Abstract / Summary

Given a positive integer, return the number you get by flipping every bit in its binary representation.

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% (400k+ submissions).

Typical patterns to solve this problem:

• Bit Manipulation

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 bitwiseComplement that returns the bitwise complement of a non-negative integer n. The complement is defined as flipping each binary digit of n (changing 0 to 1 and 1 to 0) while preserving the length of the binary representation, except for the special case when n is zero. The algorithm proceeds by explicitly extracting the bits of n, reversing their order, and then rebuilding the complemented integer using left-shift operations.

Key Steps

Detecting the zero input

The method begins with a guard clause that treats 0 as a unique input. In binary, 0 consists of a single digit 0; its complement is therefore 1. The code returns this value immediately, avoiding the subsequent bit-processing logic.

if n == 0:
    return 1

Extracting individual bits

For any positive n, the algorithm iteratively isolates the least-significant bit using the modulus operator (n % 2). Each extracted bit is appended to a list named bits. After each extraction, the integer is right-shifted (n >>= 1) to discard the processed bit. This loop continues until n becomes zero, leaving bits populated with the binary digits in reverse order (least-significant first).

bits = []
while n > 0:
    bits.append(n % 2)
    n >>= 1

Restoring original bit order

Because the bits were collected from least-significant to most-significant, the list must be reversed to reflect the natural left-to-right binary order. The reverse() method performs this in-place transformation.

bits.reverse()

Rebuilding the complemented integer

With the bits now in proper order, the method iterates over each original bit. For each iteration it left-shifts the accumulator n (which has been reset to zero after the extraction loop) to make room for the next digit, then adds the flipped value 1 - i. The expression 1 - i converts a 0 to 1 and a 1 to 0, achieving the complement operation. After processing all bits, n holds the final complemented integer, which is returned.

for i in bits:
    n <<= 1
    n += 1 - i
return n

Edge Cases

The explicit check for n == 0 ensures that the method returns the mathematically correct complement (1) rather than producing an empty bit list, which would otherwise lead to a result of 0.

When n is a power of two (for example, 8 which is 1000 in binary), the extraction loop correctly captures the solitary 1 followed by trailing zeros. The reversal step restores the leading 1 position, and the reconstruction loop flips each bit, yielding the expected complement (0111 → 7).

The algorithm also gracefully handles the maximum integer size supported by Python’s arbitrary-precision integers. Since the loop processes bits until n becomes zero, any length of binary representation is accommodated without overflow concerns.

Performance Optimizations

The implementation leverages bitwise shift operations (>>= and <<=) to move through the binary representation efficiently. Right-shifting discards processed bits without additional arithmetic, and left-shifting during reconstruction builds the result in a single pass, avoiding repeated multiplication or exponentiation.

Collecting bits into a list and then reversing it allows the algorithm to traverse the bits in natural order without recomputing positions. The use of 1 - i for flipping bits is a constant-time arithmetic operation that eliminates the need for conditional branching, contributing to a streamlined inner loop.

Overall, the method processes each binary digit exactly twice-once during extraction and once during reconstruction-resulting in a linear traversal of the bit length with minimal overhead.

Imagine a computer has a special way of reading numbers using only zeros and ones, like a secret language made of tiny light switches. Sometimes those switches are on and sometimes they are off. This code looks at a number and flips every switch. If a switch is off, it turns it on, and if it is on, it turns it off.

First, the code checks if the number is zero. If it is, it changes it to a one since zero is the opposite of one in this world. Then, it peels away the number bit by bit to see which switches are on. It puts these switches into a line so it can look at them all at once.

After that, it turns the line of switches around to get them in the right order again. Once that is done, it starts at the beginning and builds a brand-new number. It goes through each switch it found earlier and picks the opposite one. It shifts the new number over to make space and adds the new flipped switch to the end. By doing this over and over until it reaches the very last switch, the computer creates a new number that is the perfect opposite of the one it started with.

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

Time: logarithmic
As a rule of thumb, the maximum input size for one second execution time is

• factorial: up to 10 elements
• exponential: up to 20 elements
• polynomial: a few thousand elements
• loglinear: up to 100,000 elements
• linear: a few million elements
• logarithmic: a billion elements
• constant: practically unlimited

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	Python	C++		Java						TS
	WalkCCC	Python	C++		Java
	leetcode.ca	Python	C++		Java	C#		Go		Rust	TS
	LeetcodeHelp	Python	C++		Java
	Progiez	Python	C++		Java
github	BigEggStudy					C#
	black-shadows		C++
	charles-wangkai				Java
	everthis			JS
	fartem						Ruby
	fpdjsns		C++
	Garvit244	Python
	halfrost							Go
	JoshCrozier			JS
	lkwq007	Python
	Shamik07								Dart
	suxrobGM					C#
	trung-hn	Python
	varunu28				Java
	withaarzoo		C++
	YuriSpiridonov	Python
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, C#, Go, Java, Python, Rust, TypeScript
LeetcodeHelp	C++, Java, Python
Progiez	C++, Java, Python
BigEggStudy	C#
black-shadows	C++, C++
charles-wangkai	Java
everthis	JavaScript
fartem	Ruby
fpdjsns	C++
Garvit244	Python
halfrost	Go
JoshCrozier	JavaScript
lkwq007	Python
Shamik07	Dart
suxrobGM	C#
trung-hn	Python
varunu28	Java
withaarzoo	C++
YuriSpiridonov	Python

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