A row of lights stored as one number
A room has eight lights, numbered 0 to 7, and lights 0, 2 and 3 are on. A program could store the room as a list of eight true-or-false values. It could also write a 1 for each light that is on and a 0 for each light that is off, with light 0 at the right end, and read the row as one number in binary:
light 7 6 5 4 3 2 1 0on? 0 0 0 0 1 1 0 1In base 2, 13 is written 1101. With four zeros in front, that is this row, so the number 13 holds the whole room. A number used this way, as a row of yes-or-no answers, is called a bitmask, or mask for short.
The reason to store the room as a number is that a computer works on every binary digit of a number in one step. Comparing two rooms stored as lists takes eight comparisons, and comparing two numbers takes one. An integer with 64 binary digits holds 64 lights, and one operation still handles all of them.
The operations that do this are the bitwise operators: AND, OR, XOR, NOT and two shifts. This lesson teaches them on the room, and then uses them to count the 1s in a number, to find the one value in a list that has no partner, and to count the differing bits over every pair of numbers in a list.
Bits and place values
A binary digit is called a bit. We number the bits from the right, starting at 0, so bit is light . Each place is worth twice the place to its right: bit 0 is worth 1, bit 1 is worth 2, bit 2 is worth 4, and bit is worth . The value of the number is the sum of what its 1 bits are worth. In the room, bits 3, 2 and 0 are 1:
In the same way, 00101100 has 1s at bits 5, 3 and 2, so it is . This lesson writes numbers with 8 bits, which covers 0 to 255. Zeros in front do not change the value.
Definition
Bit of a nonnegative integer is its binary digit worth , counting from bit 0 at the right. A bit equal to 1 is a set bit.
AND, OR and XOR on two numbers
Suppose the room next door has lights 1 and 2 on. Its number is 00000110, which is 6. Three operators take two numbers and combine them. Each one works column by column: bit of the result depends only on bit of the two inputs.
- AND, written
a & b, has a 1 where both inputs have a 1. - OR, written
a | b, has a 1 where at least one input has a 1. - XOR, short for exclusive or and written
a ^ b, has a 1 where exactly one input has a 1, which is where the two inputs differ.
For the two rooms, those are the lights that are on in both, in at least one, and in exactly one:
| Expression | Binary | Value | Lights that are on |
|---|---|---|---|
13 | 00001101 | 13 | 0, 2, 3 |
6 | 00000110 | 6 | 1, 2 |
13 & 6 | 00000100 | 4 | 2 |
13 | 6 | 00001111 | 15 | 0, 1, 2, 3 |
13 ^ 6 | 00001011 | 11 | 0, 1, 3 |
In formulas, XOR is often written . This lesson writes ^, the way code does.
The same operators on single bits
Because no column affects another, a table of single bits describes each operator completely. Each row is one column of a larger calculation.
| a | b | a & b (AND) | a | b (OR) | a ^ b (XOR) |
|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 |
| 0 | 1 | 0 | 1 | 1 |
| 1 | 0 | 0 | 1 | 1 |
| 1 | 1 | 1 | 1 | 0 |
NOT
The fourth operator, NOT, written ~x, takes one number and flips every bit. On the eight lights it turns 00001101 into 11110010, the room with exactly the other five lights on. Which number ~13 is depends on how many bits a number has and on how negative numbers are stored, so the last part of this lesson answers it.
Try the operators on the two rooms
The playground starts on the two rooms, and . Choose an operator and check each column of the result against the single-bit table. With changed to 13 as well, a ^ b is 0, because no column differs.
XOR as addition without carries
Binary addition can be built from XOR and AND. Add two bits by hand: is 0, and are 1, and is 10 in binary, which is a 0 in this column and a carry into the next. The digit written in the column is the XOR of the two bits, and there is a carry exactly when their AND is 1. So a ^ b is the sum of two numbers with the carries left out, and a & b marks the columns that carry. A carry lands one column to the left, where it is worth twice as much, so the full sum is
a + b == (a ^ b) + 2 * (a & b)For the two rooms, , and the right side is .
Deeper read: adding with bit operators only
The identity still has a + on its right side. To remove it, treat the two numbers on the right as a new pair to add: the sum without carries, a ^ b, and the carries moved one place to the left, (a & b) << 1. (The next part covers <<; here it doubles the number.) Adding that pair can produce new carries, so we repeat until there are none. For :
a = 13 (01101) b = 6 (00110)a = 11 (01011) b = 8 (01000)a = 3 (00011) b = 16 (10000)a = 19 (10011) b = 0Two facts show that the loop ends. First, a + b is the same after every round, so b is never more than the sum. Second, zeros collect at the low end of b. The first round leaves bit 0 of b at 0. In each later round, a & b keeps every 0 of b and the shift adds one more, so after rounds the lowest bits of b are 0, and a b that is not 0 is at least . The sum 19 has 5 bits, so it is less than , and after at most 5 rounds b can only be 0. Here it took 3.
def add(a, b):
while b != 0:
carry = a & b
a = a ^ b
b = carry << 1
return a
print(add(13, 6))
print(add(200, 100))Prints 19 and 300. Both inputs must be nonnegative.
Left and right shifts
The last two operators move bits instead of combining them. A left shift by , written x << k, moves every bit places to the left and fills the right end with zeros. A right shift by , written x >> k, moves every bit places to the right, and the lowest bits fall off the end.
| Expression | Binary | Value |
|---|---|---|
13 | 00001101 | 13 |
13 << 1 | 00011010 | |
13 << 3 | 01101000 | |
13 >> 1 | 00000110 | |
13 >> 2 | 00000011 | |
1 << 5 | 00100000 |
Each place is worth twice the place to its right, so moving every bit one place to the left doubles the number, and moving every bit one place to the right halves it and drops the remainder. For a nonnegative :
Python integers grow as needed, so no bit is lost at the top: x << k is exactly x * 2**k for every .
The last row of the table shows that 1 << k is the number whose only set bit is bit .
Read and change one bit
Combining 1 << k with one operator reads or changes bit and leaves every other bit alone. Here are the four operations on the room, 13 (00001101).
Check bit k
(x >> k) & 1Examplex = 13, k = 2: 13 >> 2 = 3 (00000011), and 3 & 1 = 1, so light 2 is on
The shift moves bit down to position 0, and AND with 1 clears every other bit, so the result is 1 or 0. For no shift is needed: x & 1 is 1 when x is odd and 0 when it is even. x & (1 << k) is also nonzero exactly when bit is set, but its value is then .
Set bit k
x | (1 << k)Examplex = 13, k = 5: 13 | 32 = 45 (00101101), so light 5 is on
OR gives 1 where the second number has a 1 and keeps the bit of x everywhere else, so bit becomes 1 and the rest stay. Setting a bit that is already 1 changes nothing: 13 | 4 is still 13.
Clear bit k
x & ~(1 << k)Examplex = 13, k = 3: ~8 ends in 11110111, and 13 & ~8 = 5 (00000101), so light 3 is off
NOT turns 1 << k into a number with every bit set except bit . AND keeps the bit of x where that number has a 1 and gives 0 where it has a 0, so bit becomes 0 and the rest stay.
Flip bit k
x ^ (1 << k)Examplex = 13, k = 0: 13 ^ 1 = 12 (00001100), and 12 ^ 1 = 13 again
XOR flips the bit of x where the second number has a 1 and keeps it everywhere else, so only bit changes. Flipping the same bit twice brings it back.
Recall Light 2 of the room 13 is already on. What does `13 + (1 << 2)` do to the room, and what does `13 | (1 << 2)` do?
13 + 4 is 17, which is 00010001. Adding a 1 to a column that already holds a 1 carries, so lights 2 and 3 went off and light 4 came on. 13 | 4 is 13, because OR has no carry. Addition sets bit correctly only when the bit is known to be 0.
A number as a set
The room is a set: the set of lights that are on. Any set can be stored the same way when its possible items are numbered from 0, because then item gets bit . Our two rooms are the sets , stored as 13, and , stored as 6. Each column records whether one item is present, so the operators are the usual set operations:
| Question | Set notation | Expression | Result |
|---|---|---|---|
| In both sets | A & B | 4, the set | |
| In at least one set | A | B | 15, the set | |
| In exactly one set | A ^ B | 11, the set | |
| In A but not in B | A & ~B | 9, the set | |
| Is every item of A in B? | (A & B) == A | No: A & B is 4, not 13 |
The one-bit operations complete the list: checking bit asks whether item is in the set, setting the bit adds the item, and clearing the bit removes it.
The empty set is 0. The set of all the items 0 to is (1 << n) - 1: 1 << n is a 1 followed by zeros, and subtracting 1 turns it into ones, which for the eight lights is 255. Every number from 0 to (1 << n) - 1 is the mask of a different subset, so items have 1 << n subsets, and a loop that counts from 0 to (1 << n) - 1 visits every one of them.
A mask works when the possible items are few and numbered from 0: a 64-bit integer holds the items 0 to 63. For items with arbitrary values, such as strings, use the language's own set type.
Counting the set bits of a number
The number of lights that are on in a room is the number of set bits in its mask, three for 13. Counting set bits is our first judge problem.
You get a positive integer . Return the number of set bits in its binary representation.
Constraints
Sample 1 · Input
n = 11
Output
3
Sample 2 · Input
n = 128
Output
1
Sample 3 · Input
n = 2147483645
Output
30
In the samples, 11 is 1011 and 128 is 10000000. The third is , which is 31 ones with bit 1 switched off, so 30 bits are set.
The direct method looks at one position at a time. It adds (n >> k) & 1 to a count for and so on, and stops when n >> k is 0. That takes one step for every position up to the highest set bit: 4 steps for 11, 8 for 128 and 31 for the third sample, however few of those bits are set.
A second method takes one step per set bit, and it depends on what subtracting 1 does to a binary number. Take 44, 00101100, whose lowest set bit is bit 2. Subtracting 1 borrows from that bit: it becomes 0, the zeros below it become 1s, and the bits above it stay as they were. The result is 43, 00101011.
Now AND the two numbers. Above bit 2 they are equal, so AND keeps those bits. At bit 2 and below, every column has a 0 in one of the two numbers, so AND clears them. What is left is 40, 00101000, which is 44 without its lowest set bit.
The same argument holds for any positive number: x & (x - 1) removes the lowest set bit of x and changes nothing else. To count the set bits, we remove them one at a time and count the removals.
Count by removing the lowest set bit
def count_set_bits(n):
count = 0
while n != 0:
n &= n - 1
count += 1
return count
print(count_set_bits(11))
print(count_set_bits(128))
print(count_set_bits(2147483645))The three samples print 3, 1 and 30.
Python details
The input must not be negative. A negative Python integer has endless 1 bits at the top, as the last part of this lesson explains, so the loop would not reach 0.
128 now takes one round where the direct method took eight, and a number with one set bit takes one round however large it is.
Worked example
Trace the removals on 44
The trace runs the loop on 44 and shows n, n - 1 and their AND in binary at each round. The other inputs are 255, which takes eight rounds, 128, which takes one, and 0, which takes none.
Remove the lowest set bit repeatedly. One removal accounts for exactly one original 1 bit.
- n
- 44
- count
- 0
Change the example input
Current result: 3
The number of set bits is called the popcount of a number, short for population count. Python has it built in as n.bit_count() since version 3.10, and that is what to use outside an exercise.
Removing the lowest set bit also tests for powers of two. A power of two has exactly one set bit, so a positive is a power of two exactly when (x & (x - 1)) == 0. For example, 64 & 63 is 0.
Values that cancel under XOR
Flipping a bit twice brought it back, and whole numbers behave the same way. x ^ x is 0 for every x, because no column differs, and x ^ 0 is x. So XORing the same number into a result twice leaves the result as it was, and that is all the next problem needs.
You get a nonempty list of integers nums. Every value appears exactly twice except one, which appears once. Return that value. The solution must run in linear time and use only constant extra space.
Constraints
-
nums.length -
nums[i] - Every value appears twice except one, which appears once
Sample 1 · Input
nums = [2,2,1]
Output
1
Sample 2 · Input
nums = [4,1,2,1,2]
Output
4
Sample 3 · Input
nums = [1]
Output
1
In [4, 1, 2, 1, 2], the 1s and the 2s come in pairs and 4 does not, so the answer is 4. A hash map that counts each value would find it, but it holds an entry for every distinct value, up to 15,000 of them, and the statement allows only constant extra space.
Instead, we XOR every value into one variable that starts at 0. To see what comes out, follow one column. It starts at 0 and flips once for each value that has a 1 there, so it ends as 1 exactly when an odd number of the values have a 1 in that column. That does not depend on the order of the values, so we may work out the result as if equal values stood next to each other, where each pair cancels:
4 ^ 1 ^ 2 ^ 1 ^ 2 = 4 ^ (1 ^ 1) ^ (2 ^ 2) = 4 ^ 0 ^ 0 = 4def single_number(nums):
result = 0
for x in nums:
result ^= x
return result
print(single_number([2, 2, 1]))
print(single_number([4, 1, 2, 1, 2]))
print(single_number([1]))The three samples print 1, 4 and 1.
Negative values change nothing, because equal numbers have equal bit patterns and a pair still cancels.
The method does depend on the promise that every other value appears exactly twice, because the result records only which columns hold an odd number of 1s. XORing [1, 2, 3] gives 0, since 01, 10 and 11 put two 1s in each column, although each value appears once.
Undoing a running XOR
The next problem uses the same cancellation to take a value back out of a result.
You get a list pref. It was built from a hidden list arr of the same length, where pref[i] is the XOR of arr[0] through arr[i]. Return arr. There is always exactly one answer.
Constraints
-
pref.length -
pref[i]
Sample 1 · Input
pref = [5,2,0,3,1]
Output
[5,7,2,3,2]
Sample 2 · Input
pref = [13]
Output
[13]
In the first sample, [5, 7, 2, 3, 2] does produce pref. The running XOR is 5, then 5 ^ 7 = 2, then 2 ^ 2 = 0, then 0 ^ 3 = 3, then 3 ^ 2 = 1.
To go the other way, notice that each entry of pref is the entry before it with one more value XORed in:
pref[i] == pref[i - 1] ^ arr[i]XOR both sides with pref[i - 1]. On the right it meets itself and cancels, and arr[i] is left:
pref[i - 1] ^ pref[i] == arr[i]For that is 5 ^ 2, which is 7. The first value has nothing before it, so arr[0] is pref[0].
def find_array(pref):
arr = [pref[0]]
for i in range(1, len(pref)):
arr.append(pref[i - 1] ^ pref[i])
return arr
print(find_array([5, 2, 0, 3, 1]))
print(find_array([13]))The two samples print [5, 7, 2, 3, 2] and [13].
Counting one bit position at a time
Every bitwise operator treats each column separately, and some problems about a whole list come apart the same way: answer the question for one bit position, then add up the positions.
The Hamming distance between two integers is the number of bit positions at which they differ. You get a list of integers nums. Return the sum of the Hamming distances over every pair of numbers in the list.
Constraints
-
nums.length -
nums[i] - The answer fits in a 32-bit integer
Sample 1 · Input
nums = [4,14,2]
Output
6
Sample 2 · Input
nums = [4,14,4]
Output
4
In the first sample, 4, 14 and 2 are 0100, 1110 and 0010. Each of the three pairs differs in two positions, so the answer is . For one pair, the distance is the popcount of a ^ b, because XOR has a 1 exactly where the two numbers differ.
The direct solution computes that for every pair. The number of pairs grows with the square of the length of the list, and at the limit of 10,000 numbers there are
When we ran a plain Python loop over that many pairs, it took about 3 seconds, which would not fit a one-second limit. A list ten times as long would have 100 times as many pairs.
Now take one bit position . A pair adds 1 to the total at position when one of its numbers has bit set and the other does not. If ones of the numbers have bit set, the other n - ones have it clear, and choosing one number from each group gives every such pair once. So position adds ones * (n - ones). In the first sample, bit 1 is set in 14 and 2 but not in 4, so it adds . The figure does the same for all four positions.
[4, 14, 2], one column at a time. The outlined column is bit 1, the one worked in the text.def total_hamming_distance(nums):
n = len(nums)
total = 0
for k in range(30):
ones = 0
for x in nums:
ones += (x >> k) & 1
total += ones * (n - ones)
return total
print(total_hamming_distance([4, 14, 2]))
print(total_hamming_distance([4, 14, 4]))The two samples print 6 and 4.
The outer loop stops at 30 because is less than , so only bits 0 to 29 can be set. The program reads 30 bits from each of the 10,000 numbers:
The direct solution had 49,995,000 pairs to look at, and a list ten times as long costs this program only ten times as many checks.
Deeper read: the sum of XOR over every pair
The same split answers a related question: the sum of a ^ b over every pair. The pairs that differ at position are the same ones as before, but here each of them adds the place value instead of 1:
For [4, 14, 2], bits 3, 2 and 1 each have 2 differing pairs, which gives . Adding the three XORs directly gives as well.
Negative numbers in a fixed width
So far we have only read the bits of numbers that are zero or positive, and two questions were left open: which number ~13 is, and what bit pattern a negative number has. Both answers start from a fixed number of bits.
Take numbers of exactly 8 bits. There are patterns, which read as plain binary are the values 0 to 255. Arithmetic in 8 bits drops any carry out of bit 7, so is 0, and counting past the last pattern starts again at the first. Dropping that carry subtracts 256, so an 8-bit sum is the true sum's remainder when divided by 256: comes out as 44, because .
With that wraparound, should be the number that gives 0 when added to . The pattern for does that, because , which is 0 once the carry is dropped. Storing as that pattern is called two's complement. A short way to get the pattern is to flip every bit and then add 1: flipping gives , because and its flipped copy together set all eight bits, and adding 1 makes it .
| Step | Binary | Value in 8 bits |
|---|---|---|
| 44 | 00101100 | 44 |
| Flip every bit | 11010011 | |
| Add 1 | 11010100 | , the pattern for |
1 00000000 | 0 once the ninth bit is dropped |
The patterns of 128 to 255, the ones whose top bit is 1, are given to the negative numbers: 255 is the pattern for , since , and 128 is the pattern for , since . The pattern 128 would fit as well, and giving it to keeps every pattern with a top bit of 1 negative. So the signed values of 8 bits run from to 127 and the top bit tells the sign, while the unsigned values are the plain 0 to 255. The pattern 11010100 is 212 read as unsigned and read as signed.
The second row of the table answers the question about NOT. ~x is the pattern for , one below the pattern for , so as a signed number ~x is , and ~13 is .
The ring of 4-bit patterns
The figure arranges the sixteen patterns of 4 bits in a ring. Going clockwise adds 1. The outer numbers read each pattern as unsigned and the inner numbers as signed.
1101 with 13. One step back from 0000 is 1111, which is .Python integers have no fixed width. Python acts as if a nonnegative number had endless 0s in front and a negative number endless 1s, so ~x is there as well, and ~13 is -14.
To see a pattern in a given width, AND with a row of ones. Eight ones are 255, also written 0xFF: that is base 16, where each F stands for four 1 bits. ~13 & 0xFF is 242, the room with every light flipped.
Deeper read: the lowest set bit with x & -x
Two's complement gives one more tool for single bits. In the table, 44 is 00101100 and is 11010100. They agree at bit 2, the lowest set bit of 44, and at the zeros below it, and they are opposite at every bit above it. Flipping every bit and adding 1 always does this. After the flip, the zeros below the lowest set bit are 1s and the lowest set bit is a 0. The added 1 carries through those 1s, which turns them back into zeros, and stops at that 0, which turns it back into a 1. The bits above stay flipped.
So x & -x keeps only the lowest set bit of x, the bit that x & (x - 1) removes: 44 & -44 is 4. A Fenwick tree, a structure that keeps prefix sums of a changing array, uses x & -x to step from one stored range to the next.
Common mistakes
Using a logical operator to combine masks.
- Where it breaks
2 & 4is 0, because010and100share no set bit. The logical operator answers a different question, whether both numbers are nonzero: Python's2 and 4gives 4, and C++'s2 && 4givestrue.- The fix
- Use
&,|and^on bits. Keep the logical operators for whole conditions.
Using
^for powers.- Where it breaks
2 ^ 3is 1, not :010XOR011is001.- The fix
- Write
1 << 3for a power of two.
Leaving out parentheses.
- Where it breaks
1 << k - 1means1 << (k - 1), because-is applied before<<. For it is 4, not the row of three ones(1 << 3) - 1, which is 7. In C++,x & 1 == 0meansx & (1 == 0), which is 0 for everyx. Python reads the same text as(x & 1) == 0.- The fix
- Put parentheses around every bitwise operation that stands next to arithmetic or a comparison.
Running a bit loop on a negative number.
- Where it breaks
-1 >> 1is still , in Python and in C++, so a loop that shiftsnright until it is 0 does not end.- The fix
- Convert to a fixed width first:
n & 0xFFFFFFFF, which is 32 ones, in Python, or an unsigned type in C++.
Further reading
- USACO Guide, SilverIntro to Bitwise Operators(opens in a new tab)
The next step after this lesson. Its first problem, Codeforces 1556D Take a Guess, is solved with the addition identity, and its second, AtCoder ABC365 E Xor Sigma Problem, combines the running XOR with counting one bit position at a time. A graded problem list follows.
- Antti Laaksonen (PDF)Competitive Programmer’s Handbook, Chapter 10: Bit manipulation(opens in a new tab)
Pages 95 to 106: bit representation and the operators, sets as integers with the g++ builtin functions, then bit-parallel speedups and dynamic programming over subsets.
- cp-algorithmsBit manipulation(opens in a new tab)
The single-bit operations from this lesson, Brian Kernighan’s set-bit count, counting set bits over every number up to , and the GCC builtins.
- cp-algorithmsEnumerating submasks of a bitmask(opens in a new tab)
The loop
s = (s - 1) & mthat visits every subset of a mask, and why visiting the subsets of every mask takes steps in total. - OI Wiki, in Chinese位操作 (Bit operations)(opens in a new tab)
Operators and shifts, power-of-two tests, bit tricks for abs, min, max and swap, set-bit counting, and C++
bitset.