Reverse Bits¶
Problem¶
Given a 32-bit unsigned integer, return the integer obtained by reversing all 32 bits.
Approach¶
Bit-by-bit: extract the lowest bit of n, shift result left, OR the bit in, and shift n right. Repeat 32 times. Also includes a divide-and-conquer approach that swaps groups of bits using masks.
When to Use¶
Bit-level transformation — "reverse bits", "swap nibbles/bytes", "bit-reversal permutation" (used in FFT). Divide-and-conquer mask approach is constant-time. Also: endianness conversion.
Complexity¶
| Time | O(1) (fixed 32 iterations) |
| Space | O(1) |
Implementation¶
reverse_bits ¶
Reverse Bits — reverse the bits of a 32-bit unsigned integer.
Problem
Given a 32-bit unsigned integer, return the integer obtained by reversing all 32 bits.
Approach
Bit-by-bit: extract the lowest bit of n, shift result left, OR the bit in, and shift n right. Repeat 32 times. Also includes a divide-and-conquer approach that swaps groups of bits using masks.
When to use
Bit-level transformation — "reverse bits", "swap nibbles/bytes", "bit-reversal permutation" (used in FFT). Divide-and-conquer mask approach is constant-time. Also: endianness conversion.
Complexity
Time: O(1) (fixed 32 iterations) Space: O(1)
reverse_bits ¶
Reverse the bits of a 32-bit unsigned integer.
reverse_bits(0b00000010100101000001111010011100) 964176192 bin(reverse_bits(0b00000010100101000001111010011100)) '0b111001011110000010100101000000'
Source code in src/algo/bit_manipulation/reverse_bits.py
reverse_bits_divide_conquer ¶
Reverse bits using divide-and-conquer with bitmasks.
reverse_bits_divide_conquer(0b00000010100101000001111010011100) 964176192
Source code in src/algo/bit_manipulation/reverse_bits.py
"""Tests for reverse bits."""
from hypothesis import given
from hypothesis import strategies as st
from algo.bit_manipulation.reverse_bits import (
reverse_bits,
reverse_bits_divide_conquer,
)
class TestReverseBits:
def test_known_value(self) -> None:
assert reverse_bits(0b00000010100101000001111010011100) == 964176192
def test_all_ones(self) -> None:
assert reverse_bits(0xFFFFFFFF) == 0xFFFFFFFF
def test_zero(self) -> None:
assert reverse_bits(0) == 0
def test_one(self) -> None:
# 1 = ...0001, reversed = 1000...0 = 2^31
assert reverse_bits(1) == 1 << 31
def test_double_reverse_is_identity(self) -> None:
n = 43261596
assert reverse_bits(reverse_bits(n)) == n
class TestReverseBitsDivideConquer:
def test_known_value(self) -> None:
n = 0b00000010100101000001111010011100
assert reverse_bits_divide_conquer(n) == 964176192
def test_zero(self) -> None:
assert reverse_bits_divide_conquer(0) == 0
@given(n=st.integers(min_value=0, max_value=0xFFFFFFFF))
def test_matches_iterative(self, n: int) -> None:
assert reverse_bits_divide_conquer(n) == reverse_bits(n)
Implement it yourself
Run: just challenge bit_manipulation reverse_bits
Then implement the functions to make all tests pass.
Use just study bit_manipulation for watch mode.
Reveal Solution
reverse_bits ¶
Reverse Bits — reverse the bits of a 32-bit unsigned integer.
Problem
Given a 32-bit unsigned integer, return the integer obtained by reversing all 32 bits.
Approach
Bit-by-bit: extract the lowest bit of n, shift result left, OR the bit in, and shift n right. Repeat 32 times. Also includes a divide-and-conquer approach that swaps groups of bits using masks.
When to use
Bit-level transformation — "reverse bits", "swap nibbles/bytes", "bit-reversal permutation" (used in FFT). Divide-and-conquer mask approach is constant-time. Also: endianness conversion.
Complexity
Time: O(1) (fixed 32 iterations) Space: O(1)
reverse_bits ¶
Reverse the bits of a 32-bit unsigned integer.
reverse_bits(0b00000010100101000001111010011100) 964176192 bin(reverse_bits(0b00000010100101000001111010011100)) '0b111001011110000010100101000000'
Source code in src/algo/bit_manipulation/reverse_bits.py
reverse_bits_divide_conquer ¶
Reverse bits using divide-and-conquer with bitmasks.
reverse_bits_divide_conquer(0b00000010100101000001111010011100) 964176192