2

I am searching for an algorithm to determine which single bit (there is always only one bit set) within a 16 bit (uint16_t) variable like 0x200. I found a very nice short and effective code to do this using a lookup table for 8 bit variables, like this:

int[] lookup = {7, 0, 5, 1, 6, 4, 3, 2};

int getBitPosition(unsigned char b) {
  return lookup[((b * 0x1D) >> 4) & 0x7];
}

How to expand this for using 16 bit as input?

Paul R
  • 208,748
  • 37
  • 389
  • 560
user3503533
  • 51
  • 1
  • Note that this problem is equivalent to log2 of a number which is an exact power of 2, or "count leading zeroes", or "count trailing zeroes", or "find first set bit". See e.g. [this question](https://stackoverflow.com/q/47074126/253056) and its various duplicates. Also [this question](https://stackoverflow.com/q/21623614/253056) and its various duplicates. – Paul R Sep 18 '18 at 10:42
  • 2
    Use [ffs](https://linux.die.net/man/3/ffs) or clz functions. – KamilCuk Sep 18 '18 at 10:43
  • count the no. of times that result would've to be divided by 2 in order to get 0 – Gaurav Sep 18 '18 at 10:54
  • `int[] lookup` ==>> `int lookup[]` – Michi Sep 18 '18 at 10:57
  • @PaulR Please don't propose close posts as duplicates, it makes it hard to delete closed posts afterwards, if needed. Also, mixing in the `log` function in this isn't very helpful, since it uses floating point. – Lundin Sep 18 '18 at 11:37
  • You can also use this [function](https://stackoverflow.com/a/47324841), if you replace `unsigned char` by `uint16_t`. – wim Sep 18 '18 at 12:52
  • @Lundin: not sure I understand your first point. Note that the log2 questions are for an integer log2 for an exact power of 2, which is essentially the same as finding which bit is set - no floating point involved. – Paul R Sep 18 '18 at 13:04
  • @PaulR Essentially it goes like this: We have q1, close q2 as dupe to q1, then close q3 as dupe to q2. Now if q2 needs to be deleted for whatever reason (incorrect, off-topic etc), it's impossible, because q3 links to it. So we'd have to unravel all "duplicate chains" in order to delete it. It's like a binary tree where you can only delete leaves. Cumbersome UI. There's some meta post about it but I can't find it. – Lundin Sep 18 '18 at 13:10
  • @Lundin: OK - I *think* I understand - it sounds like a feature request might be needed to prevent this then, as it's a non-obvious problem (IMHO). – Paul R Sep 18 '18 at 13:33

1 Answers1

1

What about:

int bitset(unsigned short s)
{
    int lookup[] = {16, 1, 11, 2, 14, 12, 3, 6, 15, 10, 13, 5, 9, 4, 8, 7};
    return lookup[(((int) s*0x6F28)>>14)&15];
}

Test:

int main(void)
{
    int i, j;
    for (i = j = 1; i <= 16; ++i, j <<=1)
    {
        printf("for %5d, the %3dth bit is set\n", j, bitset(j));
    }
    return 0;
}

Gives:

for     1, the  1th bit is set
for     2, the  2th bit is set
for     4, the  3th bit is set
for     8, the  4th bit is set
for    16, the  5th bit is set
for    32, the  6th bit is set
for    64, the  7th bit is set
for   128, the  8th bit is set
for   256, the  9th bit is set
for   512, the 10th bit is set
for  1024, the 11th bit is set
for  2048, the 12th bit is set
for  4096, the 13th bit is set
for  8192, the 14th bit is set
for 16384, the 15th bit is set
for 32768, the 16th bit is set

Explanation

The first algorithm (8bits) is the following:

Build a unique number from power of two numbers (1, 2, 4...)

The incoming number s can be decomposed in bits:

s7s6s5s4s3s2s1s0, for instance, s == 4 means s2 = 1, other = 0

One number is build summing the different sx:

This operation is done by the * operation (0x1D is 11101b)

        |s7s6s5s4|s3s2s1s0    //     1b
    s7s6|s5s4s3s2|s1s0 0 0    //   100b
  s7s6s5|s4s3s2s1|s0 0 0 0    //  1000b
s7s6s5s4|s3s2s1s0| 0 0 0 0    // 10000b

Look at the number between pipe: it's unique,

  • if s is 1, the sum (between pipe) is 0b+0b+0b+1b = 1
  • if s is 2, the sum (between pipe) is 0b+0b+1b+10b = 2
  • if s is 4, the sum (between pipe) is 0b+1b+10b+100b = 7
  • if s is 8, the sum (between pipe) is 0b+10b+100b+1000b = 14

and so

The >> and & operations make the selection of the 4 middles bits.

Finally, a simple lookup table is to be applied to the unique number to get the set bit.

The 16 bits algorithm is a generalisation of this, the difficulty has been to find a combination of bits that gives unique numbers for powers of two.

Mathieu
  • 8,840
  • 7
  • 32
  • 45