bitwise operators with an if

The function supposed to count the bits that are 1 in x. I understand that the if is supposed to "mask off" the bits, but I don't understand how? Is This condition is basicly:

if(x&01==1)?

I don't understand this condition. What does (x&01) mean? Also, I don't understand when does the loop stop? whenever all the bits have been shifted to right and all the vacated cells are now 0? I just can't understand how this method works, and I looked for a solution quite a while. Thank you.

asked Dec 1, 2013 at 16:51 1,114 4 4 gold badges 15 15 silver badges 38 38 bronze badges

Have you tried debugging it step-by-step? You could understand the program by examining the values of the variables after each step.

Commented Dec 1, 2013 at 16:54

More precisely, the condition if (x & 01) is equivalent to if ((x & 01) != 0) , though in practice, the only non-zero value you can get from (x & 01) is 1. In general, if (expr) is equivalent to if ((expr) != 0) , hence my initial rewrite.

Commented Dec 1, 2013 at 16:59

@JonathanLeffler can you please explain what does the condition if (x&01) mean? I find it hard to understand. Does it compare x to 0 with & and then x with 1?

Commented Dec 1, 2013 at 17:01

If you need an explanation of bitwise operators, rather than bitwise operators in the context of an if statement, you are asking a somewhat different, noticeably larger question. 01 is an octal constant equal to 001 , '\001' , 1 , 0x1 , 0x00000001 etc, aka 'one'. The bitwise 'and' of two values compares the each bit position in each argument (in x and in 1 ), and produces a bit in the corresponding result of 1 if both are input bits are 1, and 0 otherwise. In this context, the only bit which can produce a non-zero value is the LSB, least significant bit.

Commented Dec 1, 2013 at 17:14

4 Answers 4

Let's rewrite the function using a while loop.

int bitcount(unsigned x) < int b = 0; while (x != 0) < if (x & 0x1) b++; x = x >> 1; > return b; >

Note that each iteration of the loop, we do two things:

If the bottom bit of the number is high (the number is odd), then we add one to our counter of bits.
Each iteration, we divide the number by 2 (x = x >> 1) .

answered Dec 1, 2013 at 16:56 Bill Lynch Bill Lynch 81.5k 16 16 gold badges 130 130 silver badges 177 177 bronze badges is the number hexdecimal? that's the reason you write 0x1? Commented Dec 1, 2013 at 16:58

@Alan: technically, 01 is octal, 1 is decimal, 0x01 is hexadecimal, but they all have the same value of 1 . I'm just using hex because that's how I think when I deal with shifts. It makes no difference though.

Commented Dec 1, 2013 at 16:59

thank you, but I am asking because you wrote x&0x1 and not x&01. can you please explain what this condition mean? it the most confusing thing here.

Commented Dec 1, 2013 at 17:02 Different number notations only matter to the human reader. Everything to a computer is binary. Commented Dec 1, 2013 at 17:02

You understood right about loop termination.

But however an important note: This code will work only if x is unsigned . Because for a signed integer 1 bit is appended as MSB on right shift.

It basically ANDs the value of x to decimal number 1 like this:

x: 0001000100001110 (Some random 32 bit value)
1: 0000000000000001
&
Result: 0000000000000000

Reason for this result:
AND operation does a bit by bit logical AND. You can check the truth table for AND operation on internet.

A tip/hint for you: This is not the best method to count all the 1 bits in a signed/unsigned number. There exists a method which can count 1 bits in as many loop iterations as there are number of 1 s in the number. Try yourself to implement it or search for that better method.

answered Dec 1, 2013 at 17:00 6,096 3 3 gold badges 30 30 silver badges 50 50 bronze badges

Is This condition is basicly: if(x&01==1)?

Kind of, the condition in other words: if the "x & 01" is non-zero.

Also, I don't understand when does the loop stop? whenever all the bits have been shifted to right and all the vacated cells are now 0?

When you do x>>=1, you are shifting all the bits x to the right by 1 step. If you take a pen and paper, you will also realize that this is same as dividing by 2. When will it stop? When this x becomes zero: x!=0 .

answered Dec 1, 2013 at 16:56 UltraInstinct UltraInstinct 44.2k 12 12 gold badges 83 83 silver badges 106 106 bronze badges

for example1: x's binary value is : 1011101
01's binary value is: 0000001
& is binaryopAND : ---------
result is : 0000001

for example2: x's binary value is : 1011100 (last bit is 0)
01's binary value is: 0000001
& is binaryopAND : ---------
result is : 0000000

so this means if(x&01) :
this condition returns only 2 values "0000001" or "0000000" according to x's last bit value "1" or "0".

int bitcount(unsigned x) :
x is defined as unsigned
this means x can be only a positive value.
cuz ungsigned means only positive numbers.
0000000 is NOT POSITIVE NUMBER = NOT UNSINGED NUMBER.

so b++; :
since "x" is defined in only postive numbers, x won't accept 0000000 value cuz 0000000 is a not postive number. This will only count values are 0000001.

finally x >>= 1 :
this will shift x's bits 1 slot to the right-side and will fill the new slot bit that created at the most-left with "0" value.

and x != 0 :
"for" loop will end when x comes to 0000000 in the end of process of right-side shifting eventually.