Create a mask that marks the most significant set bit, using only bitwise operators

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

SergeyL: it's too bad you deleted your answer. You could have written `+ ~0` instead of `-1` and say that "this assumes 2's complement". — , Jan 28 '14 at 18:20
Two's complement is correct to assume. I'll edit the question. — beachwood23, Jan 28 '14 at 18:21
@H2CO3 Wasn't the reason I deleted it. It returned all bits except the least significant set. — Sergey L., Jan 28 '14 at 18:22
Are we allowed the assignment operator `=`? And to assume that the size of an int is known in advance? (`32` bits?) — Paul, Jan 28 '14 at 18:34

Floris · Accepted Answer · 2014-01-28T18:52:15.620

13

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.

edited Jan 28 '14 at 18:52

answered Jan 28 '14 at 18:30

Floris

45,857
6
70
122

5

There are also `|=` and `&=` operators. – Jan 28 '14 at 18:32
2

Very elegant, I like it. – beachwood23 Jan 28 '14 at 18:35
@H2CO3 - yes, this could probably be tightened up a little bit. Not sure it would affect execution time very much. In a case like this I prefer clarity over density - it's a personal thing though. – Floris Jan 28 '14 at 18:38
2

@Floris I understand that. Just to make it clear: **I was not trying to prematurely optimize your code.** It exactly **does not affect execution time at all.** I almost always prefer readability over "efficiency" (I can't express how I hate that word). Personally, I can read compound operators more easily, but if you prefer to write it out, it's fine, I accept that. – Jan 28 '14 at 18:43
@Floris, this solution doesn't work for negative ints. – beachwood23 Jan 28 '14 at 18:45
What do you want the result to be with negative ints? They have their sign bit set, so the solution ought to be 0x80000000 right? – Floris Jan 28 '14 at 18:47
@Floris, yes for ints the solution ought to be 0x80000000. I.e., all negative ints should return -2147483648 – beachwood23 Jan 28 '14 at 18:50
The last step can be replaced by just m = m - (m >> 1). – Falk Hüffner Feb 01 '20 at 09:50

score 4 · Answer 2 · answered Jan 28 '14 at 18:31

Fill all of the bits to the right of the most significant one by shifting and OR'ing:

0b 0010 0000 0000 0000 0100 0000 0000 0000
0b 0011 0000 0000 0000 0110 0000 0000 0000
0b 0011 1100 0000 0000 0111 1000 0000 0000
0b 0011 1111 1100 0000 0111 1111 1000 0000
0b 0011 1111 1111 1111 1111 1111 1111 1111

Then shift right and add 1 to leave the most significant one:

0b 0001 1111 1111 1111 1111 1111 1111 1111
0b 0010 0000 0000 0000 0000 0000 0000 0000

Code:

int greatestBitPos(int x) {
  int is_nonzero = (x != 0);
  x = x | (x >> 1);
  x = x | (x >> 2);
  x = x | (x >> 4);
  x = x | (x >> 18);
  x = x | (x >> 16);
  return (is_nonzero * ((x >> 1) + 1));
}

I like the idea a lot. However, this problem doesn't allow the use of the `*` or `!=` operators. — beachwood23, Jan 28 '14 at 18:32
I like the `shift right and plus one` to get only the MSB. Much more elegant than my solution. — Floris, Jan 29 '14 at 00:09

score 1 · Answer 3 · answered Jan 28 '14 at 18:31

I'm still interested to see what other people can come up with, but a friend has figured out the answer.

int greatestBitPos(int x) {
  int a = x | (x >> 1);
  a = a | (a >> 2);
  a = a | (a >> 4);
  a = a | (a >> 8);
  a = a | (a >> 16);
  return ((a ^ (a >> 1)) | 0x80 << 24) & a;
}

Knowing that if we can set all bits to the right of the MSB to 1, then it becomes easy to just set the MSB and no other bits. This answer also works with negatives (with regards to twos-complement).

score 0 · Answer 4 · answered Jan 28 '14 at 18:36

0

In fact, you can use the second algorithm mentioned there, with a slight modification:

In the special case of b being of the form 0ⁿ1^m

(a > b) == !!(a & ~b)

holds.

answered Jan 28 '14 at 18:36

Brave Sir Robin

1,046
6
9

score 0 · Answer 5 · answered Aug 19 '16 at 00:27

assign a_reversed = {<<{a}};
assign a_2s_compl = (~a_reversed) + 1'b1;
assign a_lsb_set  = a_reversed & a_2s_compl;
assign a_msb_set  = {<<{a_lsb_set}};

This could all be done in one line and in a parameterizable function but I 've put all steps here to show explicitly what is happening at each step.

Create a mask that marks the most significant set bit, using only bitwise operators

5 Answers5

Linked