rywhite - 7 months ago 67

C Question

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)`

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

`<`

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`

Answer

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.