Bit Twiddling with LeetCode Problem #1342

As part of my studies at https://flatironschool.com/, I have been exploring various LeetCode problems in both Ruby and JavaScript. As a number theory enthusiast, I actively strive to find the most elegant and computationally efficient solutions.

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

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

Becomes:

  • 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̵

This is the default behavior in Ruby. Unfortunately, JavaScript doesn’t have an integer divide operation; 7 / 2 will return a float of 3.5. We could convert the float to integer via Math.floor() or parseInt(), but now we’re adding steps.

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.

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

…wait, what?

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]

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.

Full stack web developer with a passion for number theory and algorithms.

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store