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