Thursday, July 09, 2015

bitset

int has 32 bits
long has 64 bits
x /32 = x >> 5
x %32 = x & 0x1f
bitset:
    int[] a
    long max
    
    //0..n
    bitset(long n):
        if n < 0:
            throw "out of range"
        // n >> 5 is always 1 less, so add 1
        //1 11111 : 1 +1 <- no bits wasted
        //  11111 : 0 +1 <- no bits wasted
        //1 00000 : 1 +1 <- 31 bits wasted
        //  00000 : 0 +1 <- 31 bits wasted
        long size = n >> 5 +1
        max = n
        a = new int[size]
        
    set(long x):
        if x < 0 || x > max:
            throw "out of range"
        index = x >> 5
        offset = x & 0x1f
        a[index] |= (1 << offset)

    clear(long x):
        if x < 0 || x > max:
            throw "out of range"
        index = x >> 5
        offset = x & 0x1f
        a[index] &= ~(1 << offset)

    toggle(long x):
        if x < 0 || x > max:
            throw "out of range"
        index = x >> 5
        offset = x & 0x1f
        a[index] ^= (1 << offset)

    has(long x):
        if x < 0 || x > max:
            throw "out of range"
        index = x >> 5
        offset = x & 0x1f
        return ((a[index] >> offset) & 1) == 1

[Hat tip to ctci, NH]

No comments:

Post a Comment