C# getting upper 4 bits of uint32 starting with first significant bit

Question

My need is - have some (in-fact pseudo) random number of uint32, i need it's 4 first bits stating with 1st bit, which in not 0, e.g.

...000100101 => 1001

1000...0001 => 1000

...0001 => 0001

...0000 => 0000

etc I understand i have to use something like this

uint num = 1157 (some random number)
uint high = num >> offset

The problem is - i don't know where the first bit is so i can't use >> with constant variable. Can some one explain how to find this offset?

Answer 1

You can first calculate the highest significant bit (HSB) and then shift accordingly. You can this like:

int hsb = -4;
for(uint cnum = num; cnum != 0; cnum >>= 1, hsb++);
if(hsb < 0) {
    hsb = 0;
}
uint result = num >> hsb;

So we first aim to detect the index of the highest set bit (or that index minus four). We do this by incrementing hsb and shifting cnum (a copy of num) to the right, until there are no set bits anymore in cnum.

Next we ensure that there is such set bit and that it has at least index four (if not, then nothing is done). The result is the original num shifted to the right by that hsb.

If I run this on 0x123, I get 0x9 in the csharp interactive shell:

csharp> uint num = 0x123;
csharp> int hsb = -4;
csharp> for(uint cnum = num; cnum != 0; cnum >>= 1, hsb++);
csharp> if(hsb < 0) {
      >     hsb = 0;
      > }
csharp> uint result = num >> hsb;
csharp> result
9

0x123 is 0001 0010 0011 in binary. So:

0001 0010 0011
   1 001

And 1001 is 9.