Welcome to little lamb

Code » test-msb » master » tree

[master] / src / m7.c 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include <stdint.h>

typedef uint8_t  u8;
typedef uint64_t u64;

/* Niklas B.
 * https://stackoverflow.com/questions/21888140/de-bruijn-algorithm-binary-digit-count-64bits-c-sharp/21888542#21888542
 */

const u8 bitPatternToLog2[128] = {
     0, 48, -1, -1, 31, -1, 15, 51,
    -1, 63,  5, -1, -1, -1, 19, -1,
    23, 28, -1, -1, -1, 40, 36, 46,
    -1, 13, -1, -1, -1, 34, -1, 58,
    -1, 60,  2, 43, 55, -1, -1, -1,
    50, 62,  4, -1, 18, 27, -1, 39,
    45, -1, -1, 33, 57, -1,  1, 54,
    -1, 49, -1, 17, -1, -1, 32, -1,
    53, -1, 16, -1, -1, 52, -1, -1,
    -1, 64,  6,  7,  8, -1,  9, -1,
    -1, -1, 20, 10, -1, -1, 24, -1,
    29, -1, -1, 21, -1, 11, -1, -1,
    41, -1, 25, 37, -1, 47, -1, 30,
    14, -1, -1, -1, -1, 22, -1, -1,
    35, 12, -1, -1, -1, 59, 42, -1,
    -1, 61,  3, 26, 38, 44, -1, 56
};

int msb(u64 v)
{
    v |= v >> 1;
    v |= v >> 2;
    v |= v >> 4;
    v |= v >> 8;
    v |= v >> 16;
    v |= v >> 32;
    return bitPatternToLog2[(u64)(v * 0x6C04F118E9966F6BUL) >> 57];
}