Problem 476

Abstract / Summary

Given a positive integer, find the integer obtained by flipping all the bits in its binary representation.

Note

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

Python 0476.py

class Solution:
    def findComplement(self, num: int) -> int:
        mask = 1
        while mask < num:
            mask <<= 1
            mask  += 1
        return mask ^ num
7 lines | 185 bytes | submitted August 16, 2023 | GitHub   tab size 4 | low complexity

Difficulty

This problem is ranked as
easy medium hard

and has an acceptance rate of about 71% (700k+ submissions).

Typical patterns to solve this problem:
  • Bit Manipulation
I solved 663 easy, 1250 medium and 309 hard problems

AI Disclaimer

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.
LeetCode profile | GitHub repo

Code Walkthrough

Overview

The provided implementation defines a Solution class with a single method findComplement. The method receives a non-negative integer num and returns the integer that results from flipping every bit of num within the width of its most significant set bit. In other words, it computes the bitwise complement of num restricted to the minimal number of bits required to represent num in binary.

Key Steps

Initialization of the mask

The algorithm begins by creating a variable mask and setting it to the value 1. This variable will be transformed into a bit pattern consisting of all 1s that spans exactly the same width as the binary representation of num.

mask = 1

Expanding the mask to cover the full bit width

A while loop iteratively expands mask until it is at least as large as num. Inside the loop two operations are performed:

  1. mask <<= 1 shifts the current mask left by one position, effectively multiplying it by two and creating a new most-significant zero bit.
  2. mask += 1 sets that newly created least-significant bit to 1, turning the mask into a sequence of consecutive 1s.

The loop condition mask < num guarantees that the process stops as soon as the mask reaches or exceeds num. When the loop terminates, mask holds a value that is one less than the next power of two greater than num, i.e., a binary number composed entirely of 1s whose length matches the length of num.

while mask < num:
    mask <<= 1
    mask += 1

Computing the complement with XOR

After the mask has been prepared, the final step applies the XOR operator between mask and num. Because mask contains 1s in every position that should be considered, XOR flips each bit of num within that range while leaving higher bits (if any) untouched. The result of this operation is the desired complement.

return mask ^ num

Edge Cases Handled

The loop condition mask < num naturally accommodates several edge situations:

  • Zero input: When num is 0, the loop body is never executed because the initial mask value 1 is already greater than num. The mask remains 1, and the XOR operation yields 1, which is the correct complement for a single-bit representation of zero.

  • Power-of-two inputs: For values such as 1, 2, 4, 8, etc., the mask expands until it becomes exactly one less than the next power of two. For example, with num = 8 (binary 1000), the loop produces a mask of 15 (binary 1111). XOR then flips the lower four bits, delivering 7 (binary 0111), the expected complement.

  • Maximum integer size: The loop increments the mask by shifting and adding 1 until it surpasses num. Because each iteration roughly doubles the mask, the number of iterations grows logarithmically with the magnitude of num. This behavior ensures that even very large integers are processed without overflow or excessive iteration counts.

Performance Optimizations

The algorithm leverages bitwise operations that are executed directly by the processor, resulting in minimal overhead. The mask construction uses a left shift (<<=) followed by an addition of 1, which together generate a contiguous series of 1s in a single pass without needing to count bits or allocate auxiliary structures. This approach avoids the need for converting the integer to a string or list representation, thereby keeping the execution fast and memory-light.

The final XOR operation is a constant-time bitwise operation that simultaneously flips all relevant bits, eliminating the need for per-bit iteration. By combining the mask generation and the XOR step, the method achieves an efficient solution that scales well with the size of the input integer.

written by openai gpt

ELI5 - Simplified Explanation

Imagine the computer sees numbers as a long string of light switches that are either on or off. This code is like a game where the computer takes a number you give it and flips every single switch. If a switch is off, it turns on. If a switch is on, it turns off.

First, the code creates a special tool called a mask. It starts small and grows until it is just as wide as the number you gave it. Once the tool is big enough, the computer uses it to swap the switches. It is like looking at a picture through a magic lens that turns all the dark spots into bright spots and all the bright spots into dark ones. After it finishes flipping all those little switches, the new arrangement of them makes a brand new number.

written by google gemini

Code Quality

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):
n = 27 | median = 7 | μ = 6.89 | σ = 1.73

Complexity Analysis

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
generated automatically

Other Solutions

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++ Python Java TS
WalkCCC C++ Java
leetcode.ca C++ Python Java JS Go TS
LeetcodeHelp C++ Python Java
Progiez C++ Python Java
github BigEggStudy C#
black-shadows C++
chandansgowda Python
charles-wangkai Java
DimitrisJim C
everthis JS
fartem Ruby
fpdjsns C++
halfrost Go
JoshCrozier JS
keineahnung2345 C++
Krazune C
linouk23 C++
lkwq007 Python
ruoru Rust
Shamik07 Dart
sonugiri1043 C++
suxrobGM C#
trung-hn Python
varunu28 Java
vli02 C
vthwang Java
withaarzoo C++
YuriSpiridonov Python
zfang399 C++
AlgoMonster C++, Python, Java, TypeScript
WalkCCC C++, Java
leetcode.ca C++, Go, Java, JavaScript, Python, TypeScript
LeetcodeHelp C++, Java, Python
Progiez C++, Java, Python
BigEggStudy C#
black-shadows C++, C++
chandansgowda Python
charles-wangkai Java
DimitrisJim C
everthis JavaScript
fartem Ruby
fpdjsns C++
halfrost Go
JoshCrozier JavaScript
keineahnung2345 C++
Krazune C
linouk23 C++
lkwq007 Python
ruoru Rust
Shamik07 Dart
sonugiri1043 C++
suxrobGM C#
trung-hn Python
varunu28 Java
vli02 C
vthwang Java
withaarzoo C++
YuriSpiridonov Python
zfang399 C++
43 links | 30 authors | 11 languages

Videos

4 videos   did my crawler come up with invalid videos ? drop me a line.

Similar Problems

1 similar problem

Solved On The Same Day

1 easy 6 medium
8 solutions   August 16, 2023

Extra

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