# 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.

## The Problem

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.

## Wasted Iterations

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.

## Binary Preface

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

…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]

## 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

## Hamming Epilogue

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:

- 1100000
**1****[ODD]**>> 1 = 1100000 - 1100000 >> 1 = 110000
- 110000 >> 1 = 11000
- 11000 >> 1 = 1100
- 1100 >> 1 =110
- 110 >> 1 = 11
- 1
**1****[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.