Abstract / Summary

Count the number of bit flips and right shifts needed to turn a given integer into one in its binary form.

Note

The full problem description, including helpful examples, can be found on LeetCode.

This problem is ranked as

and has an acceptance rate of about 61% (200k+ submissions).

Typical patterns to solve this problem:

• Bit Manipulation
• Simulation
• String

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.

See this dedicated page for more details.

Overview

The provided Solution class implements a method numSteps that receives a binary representation of a non-negative integer as a string and returns the count of operations required to reduce that integer to 1. The allowed operations are: if the current value is even, divide it by 2; if it is odd, add 1. The algorithm works directly on the integer value after a one-time conversion from the binary string.

Key Steps

Conversion from binary string to integer

The first operation transforms the input string s into a Python integer using base-2 conversion.

n = int(s, 2)

This step enables the subsequent arithmetic and bitwise operations to be performed efficiently on a native numeric type.

Loop that drives the reduction process

A while loop continues as long as the integer n exceeds 1. Each iteration corresponds to a single allowed operation.

while n > 1:
    ...
    steps += 1

The loop guarantees termination because each iteration either halves an even number or increments an odd number, after which the next iteration will halve it.

Handling the even case

When n is even, the least-significant bit is 0. The code detects this with a bitwise AND and then right-shifts the value, which is equivalent to integer division by 2.

if (n & 1) == 0:
    n >>= 1

The right-shift operation is a low-level, constant-time manipulation that avoids the overhead of a division operation.

Handling the odd case

If n is odd, the least-significant bit is 1. The algorithm adds 1 to make the number even, preparing it for the subsequent halving in the next loop iteration.

else:
    n += 1

The addition is performed in place, keeping the memory footprint minimal.

Incrementing the step counter

Regardless of the branch taken, each loop iteration represents a single operation, so the counter steps is increased unconditionally.

steps += 1

When the loop exits, steps holds the total number of operations required to reach the value 1.

Edge Cases Handled

When the input string represents the value 1 (s == "1"), the conversion yields n == 1. The loop condition n > 1 fails immediately, and the method returns 0, correctly indicating that no operations are needed.

If the binary string corresponds to zero (s == "0"), the conversion produces n == 0. The loop again does not execute, and the method returns 0. Although zero is not a typical target for the described reduction process, the implementation gracefully handles it without error.

The use of Python’s arbitrary-precision integers means that extremely long binary strings are processed correctly; the algorithm does not rely on fixed-size integer limits, so overflow is never a concern.

Performance Optimizations

The implementation leverages bitwise operators for both parity testing and halving. The expression (n & 1) isolates the least-significant bit, providing a fast check for oddness without invoking modulo arithmetic.

Right-shifting with n >>= 1 replaces division by 2, which is computationally cheaper on most architectures and avoids the overhead of Python’s division operator.

Performing the conversion from binary string to integer once at the start eliminates repeated parsing work, allowing the loop to operate solely on numeric values.

In-place updates (n += 1 and n >>= 1) modify the existing integer object rather than creating new temporary objects, reducing memory churn and improving cache locality.

Collectively, these choices result in a tight, low-overhead loop that scales well with the size of the input number.

Imagine having a magic number written in a special code made of zeros and ones. This code starts by turning those zeros and ones into a regular number that is easier to work with. Think of the steps variable as a little counter that keeps track of how many times something happens. As long as the number is bigger than one, the computer performs a little game. It looks at the number to see if it is even. If it is even, the number gets cut in half, which is like sharing a pile of toys equally. If the number is odd, one gets added to it to make it even. Each time one of these changes happens, the counter goes up by one to mark that a move was made. The computer keeps playing this game until the number shrinks all the way down to one.

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):

not analyzed yet

I wrote a basic crawler to find other solutions to that problem.
Obviously, I did that after I solved the problem myself.

In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.

And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.

(click on a column header to sort the table)

	author
author	solutions
www	AlgoMonster	C++		Java	Python			TS
	WalkCCC	C++		Java	Python
	leetcode.ca	C++		Java	Python	Go	Rust	TS
	Progiez	C++		Java	Python
github	black-shadows	C++
	charles-wangkai			Java
	everthis		JS
	fsq	C++
	JoshCrozier		JS
	keineahnung2345	C++
	lkwq007				Python
	lzl124631x	C++
	varunu28			Java
	withaarzoo	C++
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, Go, Java, Python, Rust, TypeScript
Progiez	C++, Java, Python
black-shadows	C++, C++
charles-wangkai	Java
everthis	JavaScript
fsq	C++
JoshCrozier	JavaScript
keineahnung2345	C++
lkwq007	Python
lzl124631x	C++
varunu28	Java
withaarzoo	C++

There are a few extra pages giving you some insights into my setup:

• Tech Stack - my development environment and tools
• AI - how AI helped me create this website (NOT solving the problems)
• Progress - progression over time
• Quality - code quality