I\'m trying to understand how bits and bit manipulation works. Could someone ple
ID: 3888979 • Letter: I
Question
I'm trying to understand how bits and bit manipulation works. Could someone please explain what the following code does line by line. Say what the function is trying to do and show a representation of how it works on a 32 bit register.
/* howManyBits - return the minimum number of bits required to represent x in
* two's complement
* Examples: howManyBits(12) = 5
*/
int howManyBits(int x) {
int a = x >> 31;
int b = ((~x) &a ) + (x & ( ~a));
int c = !!(b >> 16);
int d = 8 + (c << 4);
int f = !!(b >> d);
int g = d + (~3) + (f << 3);
int h = !!(b >> g);
int i = g + (~1) + (h << 2);
int j = !!(b >> i);
int k = i + (~0) + (j<<1);
int l = !!(b >> k);
int m = k + l + !!b;
return m;
}
Explanation / Answer
Hi,
lets go line by line,
1.x>>31, this is the right shift operator which shifts bits to right by 31 places which is essentially dividing x by 2^31
for example 00001001 is given it becomes 00000000000000000000- 32 bits unless number is large, hence 0 is returned
2. b = ((~x) &a ) + (x & ( ~a)); here we are there is logical OR( (negatex and a), (x and negatea))
here since a is 0
anything &a is always 0. so the first part is useless
and aything &~a is always itself, so this always returns the number given
ex: ~12 & 0 is 0 and 12 & 1 is 12
3. !!(b >> 16)
this is again right shift as in 1st part but with double negation !! which cancels out,
basically gives us the given number divided by 2^16
4.8 + (c << 4)
now this is left shift, which is equivalent to number multiplied by 2^n
therefore 8 plus 0*2^4= 8
5. !!(b >> d)
this is same as 3. double negation which cancels out after right shift by d bits
6. d + (~3) + (f << 3),
this is left shift by 3 i.e multiply by 8 plus adding ~3 i.e -4
7. !!(b >> g) same as 5. right shift by g bits and double negation cancels out
8. g + (~1) + (h << 2)
this is left shift by 2 bits i.e multiply by 4 and adding ~1 i,e -2
9. !!(b >> i) same as 5, right shift by i bits, double negated
10. i + (~0) + (j<<1)
this is left shift by 1 that is multiplying by 2 and then adding ~0 i.e -1
11. !!(b >> k) same as 7. double negated right shift by k bits
12. k + l + !!b here again the double negation is cancelled, after that a plain addition,
Thumbs up if this was helpful, otherwise let me know in comments.