-
Notifications
You must be signed in to change notification settings - Fork 0
/
bitmap_notes
28 lines (21 loc) · 1.07 KB
/
bitmap_notes
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
Bitmap operations:
1. __builtin_ctzl(x) (unsigned long - 32 bits)
__builtin_ctzll(x) (unsigned long long - 64 bits)
Returns the number of trailing 0-bits in x, starting at the least significant bit position. If x is 0, the result is undefined.
* Similar to __builtin_ctz, except the argument type is unsigned long / unsigned long long .
2. __builtin_popcountl(x) (unsigned long - 32 bits)
__builtin_popcountll(x) (unsigned long long - 64 bits)
Returns the number of 1-bits in x.
* Similar to __builtin_popcount, except the argument type is unsigned long / unsigned long long .
3. t = x & -x
t is all 0's except at the location of last 1 in x
Example: x = 0x 0101 1010; -x = 0x 1010 0110; t = 0x 0000 0010
4. x &= x - 1
flip the last 1 in x to a 0.
Example: x = 0x 0101 1010; x - 1 = 0x 0101 1001; x & x - 1 = 0x 0101 1000
5. from article https://lemire.me/blog/2015/01/08/fast-unary-decoding/
6. x ^= (1l << n-1)
flip the n-th rightmost bit
7. i is an int64_t variable:
i ^ (1 << 31) => flip 32 bits from the left
i ^ (1l << 32) => (i >>> 32) << 32