What is the following function doing?
unsigned int foo(unsigned int x) { unsigned int c = sizeof x; c <<= 3; if(x == 0) return c; c--; while(x = x & x-1) c--; return c; }
1. unsigned int foo(unsigned int x){ 2. unsigned int c = sizeof x; 3. c <<= 3; 4. if(x == 0) return c; 5. c--; 6. while(x = x & x-1) c--; 7. return c; 8. } line no 2 : c = no of bytes for x. line no 3 : c<<=3 is c*8 which is converting Byte into bits. line no 6 : counting no of 1s and decrementing c value by 1. c will be decremented as many times as no of 1s will be in x. line no 7 : return c i.e. no of 0s or no of Unset bit in x.
c<<=3 is c*8 which is converting Byte into bits.
did not understand the above line ..
According to me it should be,
line 3 = > c= 4 // by default sizeof(int)= 4
line 4 => c = c << 3 = c * 8 = 4* 8 = 32
just to clear self doubt-
bool isPowerOfTwo(int x) { // x will check if x == 0 and !(x & (x - 1)) will check if x is a power of 2 or not return (x && !(x & (x - 1))); }
In this code will the time complexity be O(1) or O(log X), since there are log X bits to evaluate and its bitwise??
Logic behind no of set bits and decrement of c
line no 4 : c<<=3 is c*8 which is converting Byte into bits. line no 6 : decrementing c because while will run only k-1 times, where k is no of 1s in x line no 7 : counting no of 1s and decrementing c value by 1. c will be decremented k-1 times, where k is no of 1s in x. so overall after while loop, total no of 1s in x will be subtracted from c line no 8 : return c i.e. no of 0s or no of Unset bit in x.
@