# Bitwise manipulation

Discussion in 'C Programming' started by Nehil, Jul 14, 2007.

1. ### NehilGuest

how can u find whether a no has consecutive zero bits either in from
LSB or MSB.
if they exist in between, then what to do? plz clarify.

Nehil, Jul 14, 2007

2. ### Malcolm McLeanGuest

"Nehil" <> wrote in message
news:...
> how can u find whether a no has consecutive zero bits either in from
> LSB or MSB.
> if they exist in between, then what to do? plz clarify.
>

Take the binary complement of the number (~). Take two copies, and shift one
a bit (<<). Then AND (&, just one). If the answer is non-zero, you have
consecutive zero bits.

--
Free games and programming goodies.
http://www.personal.leeds.ac.uk/~bgy1mm

Malcolm McLean, Jul 14, 2007

3. ### NehilGuest

On Jul 15, 2:02 am, "Malcolm McLean" <> wrote:
> "Nehil" <> wrote in message
>
> news:...> how can u find whether a no has consecutive zero bits either in from
> > LSB or MSB.
> > if they exist in between, then what to do? plz clarify.

>
> Take the binary complement of the number (~). Take two copies, and shift one
> a bit (<<). Then AND (&, just one). If the answer is non-zero, you have
> consecutive zero bits.
>
> --
> Free games and programming goodies.http://www.personal.leeds.ac.uk/~bgy1mm

Thanks for your answer. but the solution you suggested only tells true
or false, whether consecutive zero bits are there or not.

i need something different :
i want to know how many consecutive zero bits are there?
for exapmle :
let say arr[0] = 10; so bit representation will be (32-bit)

00000000 00000000 00000000 00001010

so answer should be => 29 from MSB and 1 from LSB.
Thanks.

Nehil, Jul 14, 2007
4. ### Eric SosmanGuest

Nehil wrote:
> how can u find whether a no has consecutive zero bits either in from
> LSB or MSB.
> if they exist in between, then what to do? plz clarify.

Are you the same "Nehil" who is undertaking to write
a garbage collector for C? If so, have you ever heard the

Yes, we all know that "A man's reach should exceed his
grasp," but perhaps by not quite so wide a span ...

--
Eric Sosman
lid

Eric Sosman, Jul 14, 2007
5. ### NehilGuest

On Jul 15, 2:30 am, Eric Sosman <> wrote:
> Nehil wrote:
> > how can u find whether a no has consecutive zero bits either in from
> > LSB or MSB.
> > if they exist in between, then what to do? plz clarify.

>
> Are you the same "Nehil" who is undertaking to write
> a garbage collector for C? If so, have you ever heard the
> advice "Walk before you run?"
>
> Yes, we all know that "A man's reach should exceed his
> grasp," but perhaps by not quite so wide a span ...
>
> --
> Eric Sosman
>

===================================================================
Yes, i'm the same Nehil. but i could not understand your wordings.
i
came to this doubt in that project only. i designed a bitmap for each
page i allocate, and now want to know how many pages have been
allocated by knowing how many bits are there zero??

is this approach good?

Nehil, Jul 14, 2007
6. ### peteGuest

Nehil wrote:
>
> On Jul 15, 2:02 am, "Malcolm McLean" <> wrote:
> > "Nehil" <> wrote in message
> >
> > news:...> how can u find whether a no has consecutive zero bits either in from
> > > LSB or MSB.
> > > if they exist in between, then what to do? plz clarify.

> >
> > Take the binary complement of the number (~). Take two copies, and shift one
> > a bit (<<). Then AND (&, just one). If the answer is non-zero, you have
> > consecutive zero bits.
> >
> > --
> > Free games and programming goodies.http://www.personal.leeds.ac.uk/~bgy1mm

>
> Thanks for your answer. but the solution you suggested only tells true
> or false, whether consecutive zero bits are there or not.
>
> i need something different :
> i want to know how many consecutive zero bits are there?
> for exapmle :
> let say arr[0] = 10; so bit representation will be (32-bit)
>
> 00000000 00000000 00000000 00001010
>
> so answer should be => 29 from MSB and 1 from LSB.

/* BEGIN new.c */

#include <stdio.h>

#define N 10U
#define str(s) # s
#define xstr(s) str(s)

void consecutive_zero_bits(unsigned n, unsigned *most, unsigned *least);

int main(void)
{
unsigned most, least;

consecutive_zero_bits(N, &most, &least);
puts(xstr(N));
printf("%u from MSB and %u from LSB.\n", most, least);
return 0;
}

void consecutive_zero_bits(unsigned n, unsigned *most, unsigned *least)
{

count = 0;
if( (mask & n) == 0) {
++count;
} else {
*least = count;
break;
}
}
count = 0;
for (mask = (0u - 1) / 2 + 1; mask != 0; mask /= 2) {
if( (mask & n) == 0) {
++count;
} else {
*most = count;
break;
}
}
}

/* END new.c */

--
pete

pete, Jul 14, 2007
7. ### Malcolm McLeanGuest

"Nehil" <> wrote in message
news:...
> On Jul 15, 2:30 am, Eric Sosman <> wrote:
>> Nehil wrote:
>> > how can u find whether a no has consecutive zero bits either in from
>> > LSB or MSB.
>> > if they exist in between, then what to do? plz clarify.

>>
>> Are you the same "Nehil" who is undertaking to write
>> a garbage collector for C? If so, have you ever heard the
>> advice "Walk before you run?"
>>
>> Yes, we all know that "A man's reach should exceed his
>> grasp," but perhaps by not quite so wide a span ...
>>
>> --
>> Eric Sosman
>>

>
> ===================================================================
> Yes, i'm the same Nehil. but i could not understand your wordings.
> i
> came to this doubt in that project only. i designed a bitmap for each
> page i allocate, and now want to know how many pages have been
> allocated by knowing how many bits are there zero??
>
> is this approach good?
>

A garbage collector, let alone an efficient garbage collector, is a very
difficult routine to write. If you can't even do basic bit manipulation - no
shame on you, we were all beginners at some time - then there is no way you
are going to achieve a garbage collector, except by some miracle.

--
Free games and programming goodies.
http://www.personal.leeds.ac.uk/~bgy1mm

Malcolm McLean, Jul 15, 2007
8. ### NehilGuest

On Jul 15, 1:33 pm, "Malcolm McLean" <> wrote:
> "Nehil" <> wrote in message
>
> news:...
>
> > On Jul 15, 2:30 am, Eric Sosman <> wrote:
> >> Nehil wrote:
> >> > how can u find whether a no has consecutive zero bits either in from
> >> > LSB or MSB.
> >> > if they exist in between, then what to do? plz clarify.

>
> >> Are you the same "Nehil" who is undertaking to write
> >> a garbage collector for C? If so, have you ever heard the
> >> advice "Walk before you run?"

>
> >> Yes, we all know that "A man's reach should exceed his
> >> grasp," but perhaps by not quite so wide a span ...

>
> >> --
> >> Eric Sosman
> >>

>
> > ===================================================================
> > Yes, i'm the same Nehil. but i could not understand your wordings.
> > i
> > came to this doubt in that project only. i designed a bitmap for each
> > page i allocate, and now want to know how many pages have been
> > allocated by knowing how many bits are there zero??

>
> > is this approach good?

>
> A garbage collector, let alone an efficient garbage collector, is a very
> difficult routine to write. If you can't even do basic bit manipulation - no
> shame on you, we were all beginners at some time - then there is no way you
> are going to achieve a garbage collector, except by some miracle.
>
> --
> Free games and programming goodies.http://www.personal.leeds.ac.uk/~bgy1mm

However i've developed it myself and it is working efficiently. it was
bit manipulation that makes me nervous while thinking logic for it.
but i'll practice for it.

the allocator and de-allocator both r working fine.
Actually, the problem i asked to find some effecient solution for it.
by linear searching, i'd already done it.

thnkas all.

Nehil, Jul 15, 2007

Nehil wrote:
> how can u find whether a no has consecutive zero bits either in from
> LSB or MSB.

What does "either in from LSB or MSB" mean?

> if they exist in between, then what to do?

Between what?

> plz clarify.

I suggest that _you_ clarify.

--