find ones position in 64 bit number

Question

I'm trying to find the position of two 1's in a 64 bit number. In this case the ones are at the 0th and 63rd position. The code here returns 0 and 32, which is only half right. Why does this not work?

#include<stdio.h> void main() { unsigned long long number=576460752303423489; int i; for (i=0; i<64; i++)     {     if ((number & (1 << i))==1)         {         printf("%d  ",i);          }        } } 

Answer 1

There are two bugs on the line

if ((number & (1 << i))==1) 

which should read

if (number & (1ull << i)) 

Changing 1 to 1ull means that the left shift is done on a value of type unsigned long long rather than int, and therefore the bitmask can actually reach positions 32 through 63. Removing the comparison to 1 is because the result of number & mask (where mask has only one bit set) is either mask or 0, and mask is only equal to 1 when i is 0.

However, when I make that change, the output for me is 0 59, which still isn't what you expected. The remaining problem is that 576460752303423489 (decimal) = 0800 0000 0000 0001 (hexadecimal). 0 59 is the correct output for that number. The number you wanted is 9223372036854775809 (decimal) = 8000 0000 0000 0001 (hex).

Incidentally, main is required to return int, not void, and needs an explicit return 0; as its last action (unless you are doing something more sophisticated with the return code). Yes, C99 lets you omit that. Do it anyway.

Answer 2

Because (1 << i) is a 32-bit int value on the platform you are compiling and running on. This then gets sign-extended to 64 bits for the & operation with the number value, resulting in bit 31 being duplicated into bits 32 through 63.

Also, you are comparing the result of the & to 1, which isn't correct. It will not be 0 if the bit is set, but it won't be 1.

Shifting a 32-bit int by 32 is undefined.

Also, your input number is incorrect. The bits set are at positions 0 and 59 (or 1 and 60 if you prefer to count starting at 1).

The fix is to use (1ull << i), or otherwise to right-shift the original value and & it with 1 (instead of left-shifting 1). And of course if you do left-shift 1 and & it with the original value, the result won't be 1 (except for bit 0), so you need to compare != 0 rather than == 1.