Bit Twiddling with LeetCode Problem #1342
Whenever an opportunity for bit manipulation arises, I get particularly excited. https://en.wikipedia.org/wiki/Bit_manipulation
In a sense, bit manipulation is the meeting space between number theory and a computer’s bare metal. Within the context of an algorithm, it allows you to leverage the properties of binary arithmetic to do the heavy lifting for you.
LeetCode problem #1342 is extraordinarily simple, but it serves as a great launching point into bit shifts. https://leetcode.com/problems/number-of-steps-to-reduce-a-number-to-zero/
Given a non-negative integer
num, return the number of steps to reduce it to zero. If the current number is even, you have to divide it by 2, otherwise, you have to subtract 1 from it.
The dominant, naive solution utilizes branching and wastes an amount of loop iterations equal to the base 2 Hamming weight of num. https://en.wikipedia.org/wiki/Hamming_weight
The Naive Solution
Starting with the aforementioned, naive approach, we do exactly as the problem itself dictates: If the current number is even, you have to divide it by 2, otherwise, you have to subtract 1 from it. We iterate this logic until we’ve reduced the number to zero.
Starting with the number 7, the iterations would be as follows:
- 7 is odd, subtract 1
- 6 is even, divide by 2
- 3 is odd, subtract 1
- 2 is even, divide by 2
- 1 is odd, subtract 1
- 0 is 0, we are done.
We can make two general observations that will simplify the problem:
- Whenever we divide an even number by 2, the result may be even or odd.
- Whenever we subtract 1 from an odd number, the result will always be even.
The second observation gives us the ability to predict the future; if the number is odd, we know that it will be even on the next iteration. Rather than stepping through both iterations, we can preemptively combine their operations:
- subtract 1, add 1 step to the counter
- divide by 2, add 1 step to the counter
- subtract 1 and divide by 2, add 2 steps to the counter
We can further optimize by utilizing integer division; this will perform the “subtract by 1” for free. Recall that integer division automatically discards the remainder:
7 / 2 = 3 r̵e̵m̵a̵i̵n̵d̵e̵r̵ ̵1̵
In base 10 (decimal) notation, each number position represents a power of 10. For instance, the number 193 is actually:
193 = 1*10² + 9*10¹ + 3*10⁰
In other words: one 100 + nine 10s + three 1s
In base 2 (binary) notation, each number position represents a power of 2. That same 193 is written as 11000001.
11000001 = 1*2⁷ + 1*2⁶ + 0*2⁵ + 0*2⁴ + 0*2³ + 0*2² + 0*2¹ + 1*2⁰
In other words: one 128 + one 64 + zero 32s + zero 16s + zero 8s + zero 4s + zero 2s + one 1 = 128 + 64 + 1 = 193
The rightmost bit, termed the “least significant bit” or LSB, is worth 2⁰= 1. When you test if a number is even or odd, via num % 2, you are checking if this bit is 0 or 1.
The Binary Shift
In several languages, the binary shift operators are << and >>. We supply the number to shift, as well as how many times we want to shift it:
193 << 1 = 386
193 >> 1 = 96
Shifting to the left is the same as multiplying by 2; we shift each bit over and add a zero to the end. The operation is analogous to multiplying by 10 in decimal — we move the number left and add 0.
- 193 * 10 = 1930
- 11000001 << 1 = 110000010 = 386 base 10
Shifting to the right is the same as integer division by 2; we are shifting each bit over and discarding the LSB. The operation is analogous to integer division by 10 in decimal — we move the number right and discard the one’s place.
- 193 / 10 = 19
- 11000001 >> 1 = 1100000 = 96 base 10
We can shift as many times as we would like in a single operation:
- 193 << 4 = 3088 [effectively 193 * 2 * 2 * 2 * 2]
- 193 >> 4 = 12 [effectively 193 / 2 / 2 / 2 / 2]
The Optimized Solution
Returning to the problem at hand, let us recall the naive solution:
Refactoring, to utilize pre-emption and bit shifting:
We invoke our logical preemption by always adding 1 step and only adding a second step if the number is odd. Afterwards, we right shift and repeat.
Note the use of the shift-equals: num >>= 1
This is equivalent to num = num >> 1
By using preemption and bit shifting, we saved a loop iteration each time we encountered an odd number. Is there a way to know how many times we will encounter an odd number?
Recall that we check if a number is odd via num % 2, which is checking the LSB. When we right shift, we slide the bits right and discard that LSB. The remaining, rightmost bit is the new LSB that will be checked on the next iteration.
Therefore, we know that we will encounter an odd number for every binary ‘1’ that is present. For example, running our algorithm on the number 193:
- 11000001 [ODD] >> 1 = 1100000
- 1100000 >> 1 = 110000
- 110000 >> 1 = 11000
- 11000 >> 1 = 1100
- 1100 >> 1 =110
- 110 >> 1 = 11
- 11 [ODD] >> 1 = 1
- 1 [ODD] >> 1 = 0
The number of 1’s present in a binary number is its ‘Hamming weight’. If we know the number of digits in a binary number, as well as its Hamming weight, we can solve the problem algebraically rather than iteratively:
Note that this isn’t necessarily a faster solution in our case, as we must first convert the number to a string and run a pattern match on that string.