#include <stdint.h>

typedef uint8_t  u8;
typedef uint64_t u64;

/* Kim Walisch, Mark Dickinson
 * https://www.chessprogramming.org/BitScan#De_Bruijn_Multiplication_2
 */

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

int msb(u64 v)
{
    if (!v) return 0;

    const u64 debruijn64 = 0x03F79D71B4CB0A89UL;

    v |= v >> 1;
    v |= v >> 2;
    v |= v >> 4;
    v |= v >> 8;
    v |= v >> 16;
    v |= v >> 32;

    return index64[(v * debruijn64) >> 58] + 1;
}