We all know that bit masking is occasionally necessary if you're dealing with data at the binary level but, if you're anything like me, you use it infrequently enough that you constantly have to lookup anything beyond the basics. This is just a spot to record all of the little tricks that I've come across in one place.
The three most common operations are to get, set and clear single bits. Those are usually pretty easy to remember but for thoroughness I'll note them down here.
# Get a bit
mask = (1<<bit)
num & mask
# Set a bit
mask = (1<<bit)
num | mask
# Clear a bit
mask = (1<<bit)
num ^ maskThe key operation is taking the number 1 and moving it left into position with the left shift operator <<.
# Set the nth bit
(1<<n)
# Ex.
(1<<0) # '1'
(1<<1) # '10'
(1<<2) # '100'
(1<<3) # '1000'
(1<<4) # '10000'
(1<<5) # '100000'
(1<<6) # '1000000'Then, we use the basic bitwise operators &, | and ^ to change the original binary value. I've thrown in the other basic operators too.
1010 1010 1010 1100 1100
& 1100 | 1100 ^ 1100 << 1 >> 1 ~ 1100
------ ------ ------ ------ ------ ------
1000 1110 0110 1000 0110 0011
These aren't really that useful but can be used to help you learn more about how bit manipulation works.
# Swap two numbers without creating another variable
a = a ^ b
b = a ^ b
a = a ^ b
# Check if a number is odd or even
(num & 1) == 0 # is even
(num & 1) == 1 # is odd
# Change case of char (for C/C++)
'A' | ' ' == 'a'
'a' & '_' == 'A'Here is the "real skinny" as my dad has been saying recently for some reason. These are the things I tend to forget and that can be very useful when trying to manipulate those bits.
# Count set bits (ones) in integer
# This is Kernigan's algorithm
# Loop only iterates once for each set bit in num
def pop_count(num)
count = 0
while(num > 0)
num &= num - 1
count += 1
end
count
end# Set the first n bits
(1<<n)-1
# Ex.
(1<<1)-1 # '1'
(1<<2)-1 # '11'
(1<<3)-1 # '111'
(1<<4)-1 # '1111'
(1<<5)-1 # '11111'
(1<<6)-1 # '111111'
# Clear first n bits
mask = (1<<n)-1
(num | mask) ^ mask
# Ex.
num = 250 # '11111010'
mask = (1<<4)-1 # '00001111'
(num | mask) ^ mask # '11110000'
# Replace first n bits
mask = (1<<n)-1
num = (num | mask) ^ mask # clear n bits from num
sub &= mask # clear upper bits of sub expression
num | sub # combine the two
# Ex.
num = 250 # '11111010'
mask = (1<<4)-1 # '00001111'
num = (num | mask) ^ mask # '11110000'
sub = 85 # '01010101'
sub &= mask # '00000101'
num | sub # '11110101'# Set a range of bits a-z inclusive
((1<<a)-1) ^ ((1<<(z+1))-1)
# Conceptually similar to creating two ranges and "subtracting" the smaller from the larger
# Ex.
((1<<0)-1) ^ ((1<<(3+1))-1) # '1111'
((1<<1)-1) ^ ((1<<(4+1))-1) # '11110'
((1<<2)-1) ^ ((1<<(5+1))-1) # '111100'
((1<<3)-1) ^ ((1<<(6+1))-1) # '1111000'
((1<<4)-1) ^ ((1<<(7+1))-1) # '11110000'
((1<<5)-1) ^ ((1<<(8+1))-1) # '111100000'
# Clear bits in a range a-z inclusive
mask = ((1<<a)-1) ^ ((1<<(z+1))-1)
(num | mask) ^ mask
# Ex.
num = 251 # '11111011'
mask = ((1<<1)-1) ^ ((1<<(3+1))-1) # '00001110'
(num | mask) ^ mask # '11110001'
# Replace bits in a range a-z inclusive
mask = ((1<<a)-1) & ((1<<z)-1)
num = (num | mask) ^ mask # clear range of bits
sub = (sub<<a) & mask # clear bits not in range''
num | sub # combine the two
# Ex.
num = 251 # '11111011'
mask = ((1<<1)-1) ^ ((1<<(3+1))-1) # '00001110'
num = (num | mask) ^ mask # '11110001'
sub = 18 # '00010010'
sub = (sub<<1) & mask # '00000100'
num | sub # '11110101'