CODEWITHSUNDEEP
cbit-manipulation
user2509366
user2509366

Reputation: 35

Bitwise operations, confused with expression used in "The C programming Language"(book)

In the book I am reading to learn C "The C programming language" in chapter 2.
The book is explaining Bitwise operations and it has a function that shows how many bits are in an integer.
The following is the function...

int Bitcount(unsigned x){

    int b;
    for(b = 0; x != 0; x >>=1){
      if(x & 01){
    b++
   }
 }
 return b;
}

Then an exercise is given to us stating exactly this.
"In a two's complement number system, x &= (x-1) deletes the rightmost 1-bit in x; Explain why. Use this observation to write a faster version of Bitcount".

The problem is I really cannot understand how "x &= (x-1)" would work? can someone explain this to me? or send me to a resource that could better help me understand? I have been trying to figure this out but I really can't.

Thank you for any help that you may give.
also if there is anything wrong with my question this is my first post so please help me make my questions better.

Upvotes: 2

Views: 731

Answers (4)

Artyom
Artyom

Reputation: 3571

The problem is I really cannot understand how "x &= (x-1)" would work?

Binary number is positional the same way as decimal number. When we increase the number we carry a bit to the left, when we decrease we borrow from the left the same way we do with decimals. So in case x-01 we borrow the first 1-bit from the right while others being set to 1-bit:

     10101000
   - 00000001
     --------
     10100111

which is inversion of those bits till the first 1-bit. And as stated before by others ~y & y = 0 that is why this method can be used to count 1-bits as proposed by the book to make the method faster comparing to bits shifting.

Upvotes: 0

fvu
fvu

Reputation: 32953

X and X-1 cannot both have their rightmost bit set to 1, because in the binary system numbers ending in 0 and 1 alternate - so X & (X-1) is guaranteed to be a number whose rightmost bit set to 0 as AND only evaluates to true if both terms are true. Maybe the confusion stems from what Andrew W said, here a bitwise AND is used (which ANDs each bit individually)?

EDIT: now, as Inspired points out, this is only part of the answer as the original problem specifies that the rightmost 1-bit will get reset. As Andrew W already answered the correct version in detail, I'm not going to repeat his explanation here but I refer to his answer.

Upvotes: 4

Andrew W
Andrew W

Reputation: 4598

It is equivalent to x = x & (x-1) Here, the & is a bitwise and, not a logical and.

So here's what happens:

1) The expression on the right will be evaluated first, and that value will be stored in x.

2) Suppose x = 01001011 in binary (this isn't the case, since more than 8 bits will be used to represent x, but pretend it is for this example). Then x-1 = 01001010.

3) compute the bitwise and:

01001011 &
01001010 =
01001010

which deleted the rightmost one bit.

now suppose number didn't end with a 1 bit:

Say: x = 01001100, the (x-1) = 01001011

compute the bitwise and:

01001100 &
01001011 =
01001000

again removing the rightmost 1.

Good book by the way. I hope you enjoy it!

Upvotes: 3

nullptr
nullptr

Reputation: 11058

Let's take a closer look at the rightmost 1 bit in x: suppose x = AAAAAA10000..0, where AAAAAA are arbitrary bits. Then x-1 = AAAAAA01111..1. Bitwise AND of these two expressions gives AAAAAA00000..0. This is how it resets the rightmost non-zero bit.

Upvotes: 0

Related Questions