Lookup table of O(1)


  • 2
    L

    The code is from "Bit Twiddling Hacks" by Sean Eron Anderson.

    int hammingWeight(uint32_t n) {
        int bitsSetTable[256] = {
            // B2(n): n means n 1s from 2nd bit(0 based) to MSB.
            #define B2(n) n, n + 1, n + 1, n + 2
            #define B4(n) B2(n), B2(n + 1), B2(n + 1), B2(n + 2)
            #define B6(n) B4(n), B4(n + 1), B4(n + 1), B4(n + 2)
            B6(0), B6(1), B6(1), B6(2)
        };
        /*
        bitsSetTable[0] = 0;
        for (int i = 0; i < 256; i++) {
            bitsSetTable[i] = (i & 1) + bitsSetTable[i / 2];
        }*/
        unsigned char *p = (unsigned char*)&n;
        int c = bitsSetTable[p[0]] 
                + bitsSetTable[p[1]] 
                + bitsSetTable[p[2]] 
                + bitsSetTable[p[3]];
        return c;
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.