This was part of a larger programming assignment that was due for me last night. Couldn't figure out this problem, but I'm curious as to how it could be solved.
The function int greatestBitPos(int x) should return an int mask that marks the position of the most significant bit. If x==0, return 0. No control structures (if, while, ?:) allowed.
Example: greatestBitPos(96) = 0x40
Legal operators: ! ~ & ^ | + << >> =
This website on bit twiddling is something I used as a starting point, especially the second algorithm. However, it uses < comparisons, something this problem doesn't allow.
All ideas are welcome, thanks!
Edit: Please assume 2's complement, 32-bit integers. For all negative numbers, they have their topmost bit set, so the return value should be 0x80000000.
Updated to work for negative numbers (assuming that this should return 0x80000000 since these numbers have their top bit set )
int gbp(int n) {
// return log(2) of n
unsigned int m;
m = n;
m = m | m >> 1;
m = m | m >> 2;
m = m | m >> 4;
m = m | m >> 8;
m = m | m >> 16;
m = m & ((~m >> 1)^0x80000000);
printf("m is now %d\n", m);
return m;
}
Explanation:
Starting with any bit pattern, when we shift right by 1 and take the OR, adjacent bits will become 1. Example
00010100
00001010
--------
00011110
You repeat this until you have all ones to the right of the leading digit, by successively shifting 2, 4, 8, 16 (if you have 32 bit numbers; for larger int you keep going).
Finally you need to "strip all the other ones" by inverting the number, right shifting by 1, and taking the AND:
00011111 AND 11110000 = 00010000
and there you have it.
For negative numbers, the final manipulation ensures that you don't kill the top bit if it exists. If you wanted something else to be done with negative numbers, let me know what it is.
Collected from the Internet
Please contact [email protected] to delete if infringement.
Comments