Function to convert bit position to int

Question

I have two functions to convert Bit Position to Integer and back to Bit Position. The senior developer doesn't like that I use a loop for the IntegerToBitPosition function. Is there any way to make it better? I think it's okay, but he said "Just somebody like you could use a loop to calculate something." Only one bit can be set and if there's more than one bit set, it's okay to return the first one.

private int IntToBitPosition(int intValue)
{
  int bitValue = 1;
  if (intValue == bitValue)
  {
    return 0;
  }
  for (var bitPosition = 1; bitPosition < 32; i++)
  {
    bitValue *= 2;
    if (bitValue == intValue)
    {
       return bitPosition;
    }
  }
  return 0;
}

private int BitPositionToInt(int bitPosition)
{
  int intValue = 0;
  intValue |= 1 << bitPosition;
  return intValue;
}

Your "Senior Developer" is supposed to support, educate and *encourage* his subordinates. It sounds like he's *insulting* you. I hope I'm mistaken... — paulsm4, Dec 13 '20 at 20:56
Is "bit position" 0-based or 1-based? What should happen if a non-power-of-2 value is used as argument? — Dai, Dec 13 '20 at 21:02
I **strongly recommend** you write unit-tests for these functions before trying to implement a different solution so you can be assured of your new solution's correctness and/or to ensure you don't introduce any breaking changes. — Dai, Dec 13 '20 at 21:02
This is probably more suitable on our sister site [Code Review](https://codereview.stackexchange.com/). — 41686d6564 stands w. Palestine, Dec 13 '20 at 21:03
Also, `int intValue` - please don't use Systems Hungarian notation. It hasn't been necessary since we stopped using untyped languages. — Dai, Dec 13 '20 at 21:03
Hint: use a `switch` for `O(1)` mapping of one finite integer set to another set. — Dai, Dec 13 '20 at 21:06
@dai It is 1-based. "Only one bit can be set and if there's more than one bit set, it's okay to return the first one." It's okay to return only the first bit that matches, the solution for more than one position would be list or array of positions. — SchmidtA, Dec 13 '20 at 21:08
@Dai is "switch" better than this "for", it would be much more code? I mean i could also use recursion, but it wouldn't be nice to read. — SchmidtA, Dec 13 '20 at 21:11
@SchmidtA At risk of sounding condescending, **you have a lot to learn** if you're unfamiliar with how `switch` works. This is something that would be covered in the first week of any undergraduate course that covers C, Java, C#, even JavaScript. — Dai, Dec 13 '20 at 21:14

Dai · Answer 1 · 2020-12-13T21:19:03.097

You can use a switch statement for instant (as in O(1) time complexity) lookups of any predefined integer value - given your range is 1-32 that's straightforward:

private static int IntToBitPosition( int value )
{
    switch( value )
    {
        case 1 <<   0: return 1; // The compiler will change `1 << 0` to a constant value allowing its use in a O(1) switch.
        case 1 <<   1: return 2;
        case 1 <<   2: return 3;
        case 1 <<   3: return 4;
        case 1 <<   4: return 5;
        case 1 <<   5: return 6;
        // etc
        case 1 <<  28: return 29;
        case 1 <<  29: return 30;
        case 1 <<  30: return 31;
        case 1 <<  31: return 32;
        default      : return 0;
    }
}

If you're using Visual Studio and/or MSBuild (I assume you are) then you can save yourself the trouble of writing the switch cases by hand by using T4:

private static int IntToBitPosition( int value )
{
    switch( value )
    {
<#    for( Int32 i = 0; i <= 31; i++ ) { #>
        case << <#= ( 1 << i ) #>: return <#= i + 1 #>
<#    } #>
        default: return 0;
    }
}

Of course, more astute readers will be aware that your IntToBitPosition function is really just doing Log2(n) + 1, which can be computed instantly for any integer using this approach:

public static int Log2(int v)
{
    int r = 0xFFFF - v >> 31 & 0x10;
    v >>= r;
    int shift = 0xFF - v >> 31 & 0x8;
    v >>= shift; 
    r |= shift;
    shift = 0xF - v >> 31 & 0x4;
    v >>= shift;
    r |= shift;
    shift = 0x3 - v >> 31 & 0x2;
    v >>= shift;
    r |= shift;
    r |= (v >> 1);
    return r;
}

I don't like the switch case solution, because i don't think it's better. But the second one is. — SchmidtA, Dec 13 '20 at 21:28
@SchmidtA What makes something "better" for you? If it's performance, `switch` cannot be beat. — Dai, Dec 13 '20 at 21:58

LarryBud · Accepted Answer · 2020-12-13T21:24:39.377

Remember what binary is, the power of twos. To convert a bit to an int, it's simply 2 to the power of the bit position.

So BitPositionToInt is 2^bitPosition

So 2^4 = 16

The opposite of that is to take the log of a value with base 2. In c#, you can use the Math.Log function

e.g. if the value is 16

Math.Log(16, 2)

Which returns 4.

Note that this won't return the "first" bit position if the int isn't a value to the power of 2. If you want to do that, you still need a loop, but you can certainly simplify it.

private int IntToBitPosition(int value){
   int position=0;
   while((value & 1)==0 && value>0){
     position++;
     value= value >> 1;
   }
   return position;
}

So what we are doing here is ANDing the value with 1 to see if the 0 bit is set. If it's not, right shift the value (which divides it by 2), and check again until the bit is set, or the value is 0.

(note, I didn't typecheck the above routine, but you should get the point).

Yes with this assumption, it would be a better solution. I think it's what he meant, even if he could be more friendly. I mark it as the right answer. — SchmidtA, Dec 13 '20 at 21:22

score 0 · Answer 3 · answered Dec 13 '20 at 21:57

0

If you are targeting .NET Core 3.0 or .NET 5, you could use BitOperations.Log2(int).

private int IntToBitPosition(int intValue)
{
    return System.Numerics.BitOperations.Log2(intValue);
}

answered Dec 13 '20 at 21:57

Thinko

404
1
5
17

Function to convert bit position to int

3 Answers3