All geek questions in one place

The most efficient way to find the index of a single "1" bit in a char variable (in C)

This is an interview question:
You are given a char variable with a name chwhen you know that it represents a number that in binary form, only one of the eight bits will be equal to "1". IE, the only possible values for chare: 0x1, 0x2, 0x4, 0x8, 0x10, 0x20, 0x40, 0x80.
Given the variable ch, I need to write the most efficient code to get the index of this "1" bit. For example: if the result ch == 0x1→ is 0. If ch == 0x4→ the result is 2.

The obvious way is to use a patch case, but I need something more efficient.
Are there any bit manipulations you can do here for an efficient implementation?

+4
source share
11 answers

The variable is unsigned charsupposedly only 8 bits wide. To encode the position of the bits, we need only 3 bits. This means that we can build a 24-bit “table” containing all 8 possible 3-bit answers in natural order

111 110 101 100 011 010 001 000 =

0xFAC688

ch, , 1, 2. - ch 1, , "" ch , 3

unsigned position = (0xFAC688 / ch / ch / ch) & 0x7;

. , , , .

, , , De Bruijn. De Bruijn , "" (, ) . "" , . , De Bruijn.

24 , , De Bruijn .

, , (, , ) . De Bruijn - ch . , De Bruijn .

+3

, ch , 1 ch-1 . , , , - :

int index = ((unsigned char)ch)-1;
index = ((index & 0xAA)>>1)+(index & 0x55);  //sums of pairs of bits
index = ((index & 0xCC)>>2)+(index & 0x33);  //sums of 4s of bits
index = ((index & 0xF0)>>4)+(index & 0x0F);  //sum of 8 bits

, :

int index = indexMap[((((int)(unsigned char)ch)*DEBRUIJN)>>16)&7];

DEBRUIJN De Bruijn (https://en.wikipedia.org/wiki/De_Bruijn_sequence), , ch. indexMap .

, @rici indexMap , int.

+2

char , (, ). 0x80, unsigned char.

, , , ffs() ( ), clz() ( ) popcount() ( ), , ISO C.

, ch nibble ( ), , 32- int.

, [i] ​​ [4 * i]. , , [31:28] . , 0x01234567, , .

(Godbolt) , uchar_bitpos() .

8- char 32- int. unsigned char uint8_t, unsigned int uint32_t.

#include <stdio.h>
#include <stdlib.h>

int uchar_bitpos (unsigned char ch)
{
    unsigned int ch_pow2, ch_pow4;
    const unsigned int table =
        ((0 << 28) | (1 << 24) | (2 << 20) | (3 << 16) | 
         (4 << 12) | (5 <<  8) | (6 <<  4) | (7 <<  0));
    ch_pow2 = ch * ch;
    ch_pow4 = ch_pow2 * ch_pow2;
    return (ch_pow4 * table) >> 28;
}

int main (void)
{
    unsigned char a = 0x80;
    do {
        printf ("a = %2x   bitpos=%d\n", a, uchar_bitpos (a));
        a = a / 2;
    } while (a);
    return EXIT_SUCCESS;
}

:

a = 80   bitpos=7
a = 40   bitpos=6
a = 20   bitpos=5
a = 10   bitpos=4
a =  8   bitpos=3
a =  4   bitpos=2
a =  2   bitpos=1
a =  1   bitpos=0
+2

, "1" .

- ch , :

0x01 -> 0
0x02 -> 1
0x04 -> 2
0x08 -> 3
...

ch. 8- (char) 2 8= 256 :

char naive_table[256];

naive_table[0x01] = 0;
naive_table[0x02] = 1;
naive_table[0x04] = 2;
naive_table[0x08] = 3;
naive_table[0x10] = 4;
naive_table[0x20] = 5;
naive_table[0x40] = 6;
naive_table[0x80] = 7;

:

index = naive_table[ch];

- +

, naive_table . , ch , n - n .

, 2 8 8 -, ch .

- , . " Bruijn 1 Word" , :

A length-n , n - 2, n 0 1 , 0-1 lg n .

, 8 00011101. : 3 3- , 000, 001, 011, 111, 110, 101, 010 (), 100 ( ).

- : h (x) = (x * deBruijn) → (n - lg n)

, - :

h(ch) = ((ch * 00011101b) >> (8 - 3)) & 0x7
h(ch) = ((ch * 29) >> 5) & 0x7

ch , - , , .. :

ch    h(ch)
0x01  ((1 * 29) >> 5) & 0x7 = 0
0x02  ((2 * 29) >> 5) & 0x7 = 1
0x04  ((4 * 29) >> 5) & 0x7 = 3
0x08  ((8 * 29) >> 5) & 0x7 = 7
0x10  ((16 * 29) >> 5) & 0x7 = 6
0x20  ((32 * 29) >> 5) & 0x7 = 5
0x40  ((64 * 29) >> 5) & 0x7 = 2
0x80  ((64 * 29) >> 5) & 0x7 = 4

, - ch.

, :

char compact_table[8];

compact_table[0] = 0;
compact_table[1] = 1;
compact_table[3] = 2;
compact_table[7] = 3;
compact_table[6] = 4;
compact_table[5] = 5;
compact_table[2] = 6;
compact_table[4] = 7;

- :

h = ((ch * 29) >> 5) & 0x7;
index = compact_table[h];

- +

: . 0-7 (.. 3- ), . , .

​​ , ch - :

ch    h(sh)  index
0x01  0      0 (000b)
0x02  1      1 (001b)
0x04  3      2 (010b)
0x08  7      3 (011b)
0x10  6      4 (100b)
0x20  5      5 (101b)
0x40  2      6 (110b)
0x80  4      7 (111b)

-:

ch    h(sh)  index
0x01  0      0 (000b)
0x02  1      1 (001b)
0x40  2      6 (110b)
0x04  3      2 (010b)
0x80  4      7 (111b)
0x20  5      5 (101b)
0x10  6      4 (100b)
0x08  7      3 (011b)

, - :

011 100 101 111 010 110 001 000 = 0x72f588

, . , 3-, - 3:

h = ((ch * 29) >> 5) & 0x7; // just like before
bit_string = 0x72f588;
index = (bit_string >> (h * 3)) & 0x7;

:

index = (0x72f588 >> ((((ch * 29) >> 5) & 0x7) * 3)) & 0x7;

//, .

:

unsigned char ch;
for (ch = 1; ch; ch <<= 1) {
        int index = (0x72f588 >> ((((ch * 29) >> 5) & 7) * 3)) & 7;
        printf("ch = 0x%02x index = %d\n", ch, index);
}
return 0;
+2

:

int charindex(unsigned char c){
    union {   /* Assume both float and int are 32 bits, assume IEEE 754 floating point. */
        int i;
        float f;
    } x;
    x.f = (float)c;
    return (x.i >> 23) - 127;
}

, . gcc : gcc __builtin_ctz(), , , , charindex .

+1

.

short bit=0;
const char one=1;
while(!((ch >> bit) & one)) ++bit;

, , , , , , .

short bit=0;
const char one=1;
while(++bit < 8 && !((ch >> bit) & one)) {}

, , , , -, , .

, , , , .

short bit=
    ch&0x2?1:
    (ch&0x4?2:
    (ch&0x8?3:
    (ch&0x10?4:
    (ch&0x20?5:
    (ch&0x40?6:
    (ch&0x80?7:8))))));

, , 7- , .

short bit=
    ch&0x2?1:
    (ch&0x4?2:
    (ch&0x8?3:
    (ch&0x10?4:
    (ch&0x20?5:
    (ch&0x40?6:7)))));
0

, ( ).

.

int ch = 32
int i;
for ( i=1;ch >>i ; i++) 
  printf("%i %i \n",i, ch>>i);
printf("Final index:%i\n",i-1);

math.h log2

int l=log2((double)ch);
printf("math log2:%i\n",l);

: , , AnT. .

int ltable[256]= { -1 };

void initTable()
{
  ltable[0x01]=0;
  ltable[0x02]=1;
  ltable[0x04]=2;
  ltable[0x08]=3;
  ltable[0x10]=4;
  ltable[0x20]=5;
  ltable[0x40]=6;
  ltable[0x80]=7;
}

int lookup(size_t ch)
{
  return  ltable[ch];
}

init ASM

init():
  push rbp
  mov rbp, rsp
  mov DWORD PTR ltable[rip+4], 0
  mov DWORD PTR ltable[rip+8], 1
  mov DWORD PTR ltable[rip+16], 2
  mov DWORD PTR ltable[rip+32], 3
  mov DWORD PTR ltable[rip+64], 4
  mov DWORD PTR ltable[rip+128], 5
  mov DWORD PTR ltable[rip+256], 6
  mov DWORD PTR ltable[rip+512], 7
  nop
  pop rbp
  ret

ASM

lookup(unsigned long):
  push rbp
  mov rbp, rsp
  mov QWORD PTR [rbp-8], rdi
  mov rax, QWORD PTR [rbp-8]
  mov eax, DWORD PTR ltable[0+rax*4]
  pop rbp
  ret


 1 16 
 2 8 
 3 4 
 4 2 
 5 1 
 Final index:5
 math log2:5
 Lookup[32]=>5
0

, 7 3.

assert((n & n-1) == 0);
if(n & 0x0F) {
    if(n & 0x03){
        if(n & 0x01){
            idx = 0;
        }
        else{
            idx = 1;
        }
    }else{
        if(n & 0x04){
            idx = 2;
        }
        else{
            idx = 4;
        }
    }
}else{
    if(n & 0x30){
        if(n & 0x10){
            idx = 3;
        }
        else{
            idx = 4;
        }
    }else{
        if(n & 0x40){
            idx = 5;
        }
        else{
            idx = 6;
        }
    }
}
0

( ) popcount, C- __builtin_popcount().

, popcount(x - 1), (1 < n) (1 < 1)).. 1 0, x == 1, , n.

"Bit Scan Forward", , , x86, popcount. HW...

0

, 1, , 2. , log ch. , 2.

0

, .

:

#include <math.h>

int leadingbit(unsigned char c) {
    return log2(c);
}

:

int leadingbit(unsigned char c) {
#define N(x) ((076543210 / (x) / (x) / (x)) & 7)
#define N8(x) N(x), N(x+1), N(x+2), N(x+3), N(x+4), N(x+5), N(x+6), N(x+7)
#define N32(x) N8(x), N8(x+8), N8(x+16), N8(x+24)
    static unsigned char table[256] = {
        N32(0), N32(32), N32(64), N32(96), N32(128), N32(160), N32(192), N32(224),
    };
#undef N
#undef N8
#undef N32
    return table[c];
}

, :

int leadingbit(unsigned char c) {
    int n = c - 1;
    n = ((n & 0xAA) >> 1) + (n & 0x55);  //sums of pairs of bits
    n = ((n & 0xCC) >> 2) + (n & 0x33);  //sums of 4s of bits
    return ((n >> 4) + n) & 7;
}

builtin_clz() (, ):

#include <limits.h>

int leadingbit(unsigned char c) {
    return CHAR_BIT * sizeof(unsigned) - 1 - builtin_clz((unsigned)c);
}

Note that all of the above assumes that cthe degree 2, behavior for other values ​​is potentially undefined. You can check what cis a degree 2with a simple expression:

if (c && !(c & (c - 1))) {
    /* c is a power of 2 */
}
0
source

Source: https://habr.com/ru/post/1689347/

More articles:


All Articles