25. Reverse Bits

easyAsked at Datadog

Reverse the bits of a 32-bit unsigned integer. Datadog uses this to test bit-twiddling and the cached-lookup-table trick — exactly the pattern they use for hash-mixing in their high-cardinality tag IDs.

By Alex Chen, Founder, InterviewChamp.AI · Last verified 2026-05-20

Source citations

Public interview reports confirming this problem appears in Datadog loops.

Glassdoor (2026-Q1)— Datadog backend infra round — bit manipulation.

Problem

Reverse bits of a given 32-bit unsigned integer. Note: In some languages, there is no unsigned integer type. In that case, both input and output will be given as a signed integer type. They should not affect your implementation, as the integer's internal binary representation is the same, whether it is signed or unsigned.

Constraints

The input must be a binary string of length 32.

Examples

Example 1

Input

n = 00000010100101000001111010011100

Output

00111001011110000010100101000000

Explanation: Input represents 43261596, output represents 964176192.

Example 2

Input

n = 11111111111111111111111111111101

Output

10111111111111111111111111111111

Approaches

1. String reverse

Convert to binary string, pad to 32, reverse, parse.

Time: O(32)
Space: O(32)

function reverseBits(n) {
  return parseInt(n.toString(2).padStart(32, '0').split('').reverse().join(''), 2);
}

Tradeoff: Works but signals you avoid bit ops. Datadog will push for bitwise.

2. Bitwise shift-and-OR (optimal)

Loop 32 times. Each iteration: shift result left by 1, OR with (n & 1), shift n right by 1.

Time: O(32)
Space: O(1)

function reverseBits(n) {
  let result = 0;
  for (let i = 0; i < 32; i++) {
    result = (result << 1) | (n & 1);
    n = n >>> 1;
  }
  return result >>> 0;
}

Tradeoff: Bitwise, in-place. Datadog-canonical pattern; the trailing >>> 0 forces unsigned interpretation in JS.

Datadog-specific tips

Datadog will probe whether you understand JS's signed-vs-unsigned quirks. The `>>> 0` cast forces unsigned 32-bit; without it, the answer can come out negative. They'll also ask: 'What if you have to call this billions of times?' Answer: cache a 256-entry byte-reverse lookup table and process 8 bits at a time.

Common mistakes

Forgetting >>> 0 at the end — returns a negative number when the high bit ends up set.
Using >> (arithmetic) instead of >>> (logical) when shifting n — bleeds sign bit into the result.
Not padding to 32 bits in the string approach — leading zeros lost.

Follow-up questions

An interviewer at Datadog may pivot to one of these next:

Number of 1 Bits (LC 191) — pop-count variant.
Hamming Distance (LC 461) — XOR + popcount.
Cache a byte-reverse lookup table to amortize over many calls.

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

FAQ

Why >>> 0?

JavaScript bitwise ops produce signed 32-bit results. >>> 0 reinterprets the bit pattern as unsigned, which is what the problem wants.

When would you use a lookup table?

If you'll call this in a hot loop. Precompute 256 byte-reversals; process the 32-bit number as 4 bytes; that's 4 table lookups + 3 shifts.

Practice these live with InterviewChamp.AI

Drill Reverse Bits and other Datadog interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →