Scribd Logo
Upload

Welcome to Scribd!

  • 61 views

    Bit Hacks

    Uploaded by

    Ravi Kanth
    The document discusses various bit manipulation algorithms and techniques. It begins by describing naive and optimized approaches to counting the number of bits set in an integer. It then covers algorithms for copying the highest set bit to lower bits, finding the log base 2 of an integer, determining the next power of 2, and checking if a number is a power of 2. The document compares the performance of different algorithms and implementations.

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd

    Bit Hacks

    Uploaded by

    Ravi Kanth
    61 views44 pages
    The document discusses various bit manipulation algorithms and techniques. It begins by describing naive and optimized approaches to counting the number of bits set in an integer. It then covers algorithms for copying the highest set bit to lower bits, finding the log base 2 of an integer, determining the next power of 2, and checking if a number is a power of 2. The document compares the performance of different algorithms and implementations.

    Original Description:

    done

    Copyright

    © © All Rights Reserved

    Available Formats

    PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    The document discusses various bit manipulation algorithms and techniques. It begins by describing naive and optimized approaches to counting the number of bits set in an integer. It then covers algorithms for copying the highest set bit to lower bits, finding the log base 2 of an integer, determining the next power of 2, and checking if a number is a power of 2. The document compares the performance of different algorithms and implementations.

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    61 views44 pages

    Bit Hacks

    Uploaded by

    Ravi Kanth
    The document discusses various bit manipulation algorithms and techniques. It begins by describing naive and optimized approaches to counting the number of bits set in an integer. It then covers algorithms for copying the highest set bit to lower bits, finding the log base 2 of an integer, determining the next power of 2, and checking if a number is a power of 2. The document compares the performance of different algorithms and implementations.

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    of 44

    Bit Twiddling Hacks

    Integers

    David Barina

    March 28, 2014

    David Barina

    Bit Hacks

    March 28, 2014

    1 / 41

    Counting bits set: naive

    unsigned x;
    unsigned c;
    for(c = 0; x; x >>= 1)
    {
    c += x & 1;
    }
    a.k.a. population count, popcount

    David Barina

    Bit Hacks

    March 28, 2014

    2 / 41

    Counting bits set: Kernighan

    for(c = 0; x; c++)
    {
    x &= x - 1;
    }

    David Barina

    Bit Hacks

    March 28, 2014

    3 / 41

    Counting bits set: Kernighan

    x
    x-1
    x&(x-1)
    x
    x-1
    x&(x-1)

    David Barina

    Bit Hacks

    March 28, 2014

    4 / 41

    Counting bits set: in parallel

    x
    x
    x
    c

    -= x
    = (x
    = (x
    = (x

    >> 1 & 0U/3;


    & 0U/15*3) + (x >> 2 & 0U/15*3);
    + (x >> 4)) & 0U/255*15;
    * (0U/255)) >> (sizeof(unsigned) - 1) * CHAR_BIT;

    David Barina

    Bit Hacks

    March 28, 2014

    5 / 41

    Counting bits set

    x
    x
    x
    c

    -= x
    = (x
    = (x
    = (x

    >> 1 & 0U/3;


    & 0U/15*3) + (x >> 2 & 0U/15*3);
    + (x >> 4)) & 0U/255*15;
    * (0U/255)) >> (sizeof(unsigned) - 1) * CHAR_BIT;

    David Barina

    Bit Hacks

    March 28, 2014

    6 / 41

    Counting bits set

    x
    x>>1

    &~0U/3
    0..2

    David Barina

    11
    10
    01
    00

    Bit Hacks

    01
    01
    00
    00

    =
    =
    =
    =

    10
    01
    01
    00

    =
    =
    =
    =

    2
    1
    1
    0

    March 28, 2014

    7 / 41

    Counting bits set

    x
    x
    x
    c

    -= x
    = (x
    = (x
    = (x

    >> 1 & 0U/3;


    & 0U/15*3) + (x >> 2 & 0U/15*3);
    + (x >> 4)) & 0U/255*15;
    * (0U/255)) >> (sizeof(unsigned) - 1) * CHAR_BIT;

    David Barina

    Bit Hacks

    March 28, 2014

    8 / 41

    Counting bits set

    x
    &~0U/15*3
    x
    +

    x>>2
    &~0U/15*3
    0..4

    David Barina

    Bit Hacks

    March 28, 2014

    9 / 41

    Counting bits set

    x
    x
    x
    c

    -= x
    = (x
    = (x
    = (x

    >> 1 & 0U/3;


    & 0U/15*3) + (x >> 2 & 0U/15*3);
    + (x >> 4)) & 0U/255*15;
    * (0U/255)) >> (sizeof(unsigned) - 1) * CHAR_BIT;

    David Barina

    Bit Hacks

    March 28, 2014

    10 / 41

    Counting bits set

    x>>4
    &~0U/255*15
    0..8

    David Barina

    Bit Hacks

    March 28, 2014

    11 / 41

    Counting bits set

    x
    x
    x
    c

    -= x
    = (x
    = (x
    = (x

    >> 1 & 0U/3;


    & 0U/15*3) + (x >> 2 & 0U/15*3);
    + (x >> 4)) & 0U/255*15;
    * (0U/255)) >> (sizeof(unsigned) - 1) * CHAR_BIT;

    David Barina

    Bit Hacks

    March 28, 2014

    12 / 41

    Counting bits set

    0..8 0..8 0..8 0..8


    1

    x
    ~0U/255

    0..8 0..8 0..8 0..8


    0..8 0..8 0..8 0..8
    0..8 0..8 0..8 0..8
    0..8 0..8 0..8 0..8
    0..32
    0..32

    David Barina

    Bit Hacks

    >>24

    March 28, 2014

    13 / 41

    Counting bits set

    algorithm
    naive
    Kernighan
    parallel

    time
    30.943180 ns
    17.374596 ns
    4.136793 ns

    speedup 7.5

    David Barina

    Bit Hacks

    March 28, 2014

    14 / 41

    Copy the highest set bit to all of the lower bits

    x
    x
    x
    x
    x

    |=
    |=
    |=
    |=
    |=

    x
    x
    x
    x
    x

    >> 1;
    >> 2;
    >> 4;
    >> 8;
    >> 16;

    a.k.a. copymsb

    David Barina

    Bit Hacks

    March 28, 2014

    15 / 41

    Copy the highest set bit to all of the lower bits

    x>>1
    x|=x>>1

    x>>2
    x|=x>>2

    David Barina

    x>>4
    x|=x>>4

    Bit Hacks

    March 28, 2014

    16 / 41

    Copy the highest set bit to all of the lower bits

    unsigned shift = 1;
    while(shift < sizeof(int) * CHAR_BIT)
    {
    x |= x >> shift;
    shift <<= 1;
    }

    David Barina

    Bit Hacks

    March 28, 2014

    17 / 41

    Copy the highest set bit to all of the lower bits

    algorithm
    unroll
    loop

    time
    3.687508 ns
    3.689689 ns

    speedup 1.0

    David Barina

    Bit Hacks

    March 28, 2014

    18 / 41

    Find the log base 2 of an integer

    log2 (x) = 1

    x <1

    blog2 (x)c = dlog2 (x + 1)e 1


    dlog2 (x)e = blog2 (x 1)c + 1

    David Barina

    Bit Hacks

    March 28, 2014

    19 / 41

    Find the log base 2 of an integer: IEEE double

    unsigned x;
    unsigned r;
    r = (unsigned)ceil(log2((double)x));
    r = (unsigned)floor(log2((double)x));

    David Barina

    Bit Hacks

    March 28, 2014

    20 / 41

    Find the log base 2 of an integer: naive way (floor)

    unsigned r = 0;
    while(x >>= 1)
    {
    r++;
    }

    David Barina

    Bit Hacks

    March 28, 2014

    21 / 41

    Find the log base 2 of an integer: fast way (floor)

    unsigned r;
    unsigned shift;
    r =
    (x >
    shift = (x >
    shift = (x >
    shift = (x >

    David Barina

    0xFFFF)
    0xFF )
    0xF
    )
    0x3
    )

    <<
    <<
    <<
    <<

    4;
    3;
    2;
    1;

    x
    x
    x
    x

    >>=
    >>=
    >>=
    >>=

    Bit Hacks

    r;
    shift; r |= shift;
    shift; r |= shift;
    shift; r |= shift;
    r |= (x >> 1);

    March 28, 2014

    22 / 41

    Find the log base 2 of an integer: fast way (floor)


    x
    x>0xFFFF
    x>>16, r+=16
    x>0xFF
    x>>8,

    r+=8

    x>0xF
    x>>4,

    r+=4

    x>0x3

    David Barina

    Bit Hacks

    x>>2,

    r+=2

    x>>1,

    r+=1

    March 28, 2014

    23 / 41

    Find the log base 2 of an integer: popcount (ceil)

    x--;
    x = copymsb(x); // next pow2 minus 1
    r = popcount(x);

    David Barina

    Bit Hacks

    March 28, 2014

    24 / 41

    Find the log base 2 of an integer: popcount (ceil)

    x
    r

    David Barina

    x = copy MSB
    r = popcount

    Bit Hacks

    March 28, 2014

    25 / 41

    Find the log base 2 of an integer: DeBruijn (floor)

    static const int MultiplyDeBruijnBitPosition[32] =


    {
    0, 9, 1, 10, 13, 21, 2, 29,
    11, 14, 16, 18, 22, 25, 3, 30,
    8, 12, 20, 28, 15, 17, 24, 7,
    19, 27, 23, 6, 26, 5, 4, 31
    };
    x = copymsb(x); // next pow2 minus 1
    r = MultiplyDeBruijnBitPosition[
    (unsigned)(x * 0x07C4ACDDU) >> 27];

    David Barina

    Bit Hacks

    March 28, 2014

    26 / 41

    Find the log base 2 of an integer: fast loop (floor)


    const unsigned int b[] = {
    0x2, 0xC, 0xF0, 0xFF00, 0xFFFF0000 };
    const unsigned int S[] = { 1, 2, 4, 8, 16 };
    register unsigned int r = 0;
    for(int i = 4; i >= 0; i--)
    {
    if(x & b[i])
    {
    x >>= S[i];
    r |= S[i];
    }
    }

    David Barina

    Bit Hacks

    March 28, 2014

    27 / 41

    Find the log base 2 of an integer: table (floor)


    static const char LogTable256[256] =
    {
    #define LT(n) n, n, n, n, n, n, n, n, n, n, n, n, n, n, n, n
    -1,
    0,
    1, 1,
    2, 2, 2, 2,
    3, 3, 3, 3, 3, 3, 3, 3,
    LT(4),
    LT(5), LT(5),
    LT(6), LT(6), LT(6), LT(6),
    LT(7), LT(7), LT(7), LT(7),
    LT(7), LT(7), LT(7), LT(7)
    #undef LT
    };
    David Barina

    Bit Hacks

    March 28, 2014

    28 / 41

    Find the log base 2 of an integer: table (floor)


    if(t = x >>
    {
    r =
    }
    else if(t =
    {
    r =
    }
    else if(t =
    {
    r =
    }
    else
    {
    r =
    }
    David Barina

    24)
    24 + LogTable256[t];
    x >> 16)
    16 + LogTable256[t];
    x >> 8)
    8 + LogTable256[t];

    LogTable256[x];

    Bit Hacks

    March 28, 2014

    29 / 41

    Find the log base 2 of an integer

    algorithm
    double
    naive
    fast
    popcount
    DeBruijn
    fast loop
    table

    floor
    64.648230 ns
    20.249388 ns
    12.542725 ns
    8.794856 ns
    4.519947 ns
    3.784315 ns
    1.834092 ns

    ceil
    64.569502 ns
    20.179684 ns
    12.199326 ns
    8.409071 ns
    4.809108 ns
    3.716202 ns
    1.835536 ns

    speedup > 35

    David Barina

    Bit Hacks

    March 28, 2014

    30 / 41

    Next power of 2: copymsb

    x--;
    x = copymsb(x);
    x++;

    David Barina

    Bit Hacks

    March 28, 2014

    31 / 41

    Next power of 2: table

    x = 1 << ceil_log2(x);

    David Barina

    Bit Hacks

    March 28, 2014

    32 / 41

    Next power of 2

    algorithm
    copymsb
    log2 table

    time
    3.976506 ns
    2.169806 ns

    speedup > 1.8

    David Barina

    Bit Hacks

    March 28, 2014

    33 / 41

    Is power of 2

    if( 0 == (x & (x-1)) )


    {
    // ...
    }

    David Barina

    Bit Hacks

    March 28, 2014

    34 / 41

    Select minimum, maximum: naive

    (x < y) ? x : y
    (x > y) ? x : y

    David Barina

    Bit Hacks

    March 28, 2014

    35 / 41

    Select minimum, maximum: xor

    (((x-y) >> (sizeof(int)*CHAR_BIT-1)) & (xy)) y


    (((x-y) >> (sizeof(int)*CHAR_BIT-1)) & (yx)) x
    x = y
    y = y
    (-z) >>
    (+z) >>

    (xy)
    0
    31 = 0xffffffff
    31 = 0x00000000

    David Barina

    Bit Hacks

    March 28, 2014

    36 / 41

    Select minimum, maximum

    algorithm
    naive
    xor

    min
    1.509076 ns
    2.035053 ns

    max
    1.503108 ns
    1.847343 ns

    speedup 0.7

    David Barina

    Bit Hacks

    March 28, 2014

    37 / 41

    Absolute value (32-bit)

    // stdlib.h
    printf("%i\n", abs(+1000000000));
    printf("%i\n", abs(-1000000000));
    printf("%i\n", abs(-2147483648));

    David Barina

    Bit Hacks

    March 28, 2014

    38 / 41

    Absolute value (32-bit)

    // stdlib.h
    printf("%i\n", abs(+1000000000));
    printf("%i\n", abs(-1000000000));
    printf("%i\n", abs(-2147483648));
    1000000000
    1000000000
    -2147483648

    David Barina

    Bit Hacks

    March 28, 2014

    38 / 41

    Negate (32-bit)

    // negate all bits and add "1"


    printf("%i\n", negate(+1000000000));
    printf("%i\n", negate(-1000000000));
    printf("%i\n", negate(-2147483648));

    David Barina

    Bit Hacks

    March 28, 2014

    39 / 41

    Negate (32-bit)

    // negate all bits and add "1"


    printf("%i\n", negate(+1000000000));
    printf("%i\n", negate(-1000000000));
    printf("%i\n", negate(-2147483648));
    -1000000000
    1000000000
    -2147483648

    David Barina

    Bit Hacks

    March 28, 2014

    39 / 41

    Overflow (32-bit and 64-bit)

    printf("%i\n", (int)+2147483648); // long int => int


    printf("%li\n", +2147483648); // long int

    David Barina

    Bit Hacks

    March 28, 2014

    40 / 41

    Overflow (32-bit and 64-bit)

    printf("%i\n", (int)+2147483648); // long int => int


    printf("%li\n", +2147483648); // long int
    -2147483648
    2147483648

    David Barina

    Bit Hacks

    March 28, 2014

    40 / 41

    Sources

    x86, Intel Core2 Quad @ 2.00 GHz


    gcc 4.8 -O3
    https://www.google.com/?q=Bit+Twiddling
    http://graphics.stanford.edu/seander/bithacks.html
    http://www.fefe.de/intof.html

    David Barina

    Bit Hacks

    March 28, 2014

    41 / 41

    You might also like