190. Reverse bits

190_solution1_sequential.c

#include <stdint.h>

uint32_t reverseBits(uint32_t n) {
  uint32_t res = 0;
  for (int i = 0; i < 32; i++) {
    uint32_t bit = (n >> i) & 1;
    res = (res << 1) | bit;
  }
  return res;
}

190_solution2_divideAndConquer.c

// Swap the two 16-bit halves.
// Within each half, swap the 8-bit halves.
// Then swap 4-bit groups, then 2-bit groups, then single bits
#include <stdint.h>

uint32_t reverseBits(uint32_t n) {
  uint32_t x = n;
  x = (x >> 16) | (x << 16);
  x = ((x & 0xFF00FF00) >> 8) | ((x & 0x00FF00FF) << 8);
  x = ((x & 0xF0F0F0F0) >> 4) | ((x & 0x0F0F0F0F) << 4);
  x = ((x & 0xCCCCCCCC) >> 2) | ((x & 0x33333333) << 2);
  x = ((x & 0xAAAAAAAA) >> 1) | ((x & 0x55555555) << 1);
  return x;
}

190_solution1_sequential.cpp

#include <cstdint>

using namespace std;

class Solution {
public:
  int reverseBits(int n) {
    uint32_t x = n, res = 0;
    for (int i = 0; i < 32; i++) {
      int bit = (x >> i) & 1;
      res = (res << 1) | bit;
    }
    return res;
  }
};

190_solution2_divideAndConquer.cpp

// Swap the two 16-bit halves.
// Within each half, swap the 8-bit halves.
// Then swap 4-bit groups, then 2-bit groups, then single bits
#include <cstdint>

using namespace std;

class Solution {
public:
  int reverseBits(int n) {
    uint32_t x = n;
    x = (x >> 16) | (x << 16);
    x = ((x & 0xFF00FF00) >> 8) | ((x & 0x00FF00FF) << 8);
    x = ((x & 0xF0F0F0F0) >> 4) | ((x & 0x0F0F0F0F) << 4);
    x = ((x & 0xCCCCCCCC) >> 2) | ((x & 0x33333333) << 2);
    x = ((x & 0xAAAAAAAA) >> 1) | ((x & 0x55555555) << 1);
    return x;
  }
};

190_solution1_sequential.go

package bitmanipulation

func reverseBits(num uint32) uint32 {
    var res uint32
    for i := 0; i < 32; i++ {
        bit := (num >> i) & 1
        res = (res << 1) | bit
    }
    return res
}

190_solution2_divideAndConquer.go

// Swap the two 16-bit halves.
// Within each half, swap the 8-bit halves.
// Then swap 4-bit groups, then 2-bit groups, then single bits
package bitmanipulation

func reverseBits(num uint32) uint32 {
    x := num
    x = (x >> 16) | (x << 16)
    x = ((x & 0xFF00FF00) >> 8) | ((x & 0x00FF00FF) << 8)
    x = ((x & 0xF0F0F0F0) >> 4) | ((x & 0x0F0F0F0F) << 4)
    x = ((x & 0xCCCCCCCC) >> 2) | ((x & 0x33333333) << 2)
    x = ((x & 0xAAAAAAAA) >> 1) | ((x & 0x55555555) << 1)
    return x
}

190_solution1_sequential.java

class Solution {
    public int reverseBits(int n) {
        int res = 0;
        for (int i = 0; i < 32; i++) {
            int bit = (n >>> i) & 1; // >>> shifts in zeros, unlike >>
            res = (res << 1) | bit;
        }
        return res;
    }
}

190_solution2_divideAndConquer.java

// Swap the two 16-bit halves.
// Within each half, swap the 8-bit halves.
// Then swap 4-bit groups, then 2-bit groups, then single bits
class Solution {
    public int reverseBits(int n) {
        int x = n; // >>> shifts in zeros, unlike >>
        x = (x >>> 16) | (x << 16);
        x = ((x & 0xFF00FF00) >>> 8) | ((x & 0x00FF00FF) << 8);
        x = ((x & 0xF0F0F0F0) >>> 4) | ((x & 0x0F0F0F0F) << 4);
        x = ((x & 0xCCCCCCCC) >>> 2) | ((x & 0x33333333) << 2);
        x = ((x & 0xAAAAAAAA) >>> 1) | ((x & 0x55555555) << 1);
        return x;
    }
}

190_solution1_sequential.js

/**
 * @param {number} n - a positive integer
 * @return {number} - a positive integer
 */
var reverseBits = function (n) {
  let res = 0;
  for (let i = 0; i < 32; i++) {
    const bit = (n >>> i) & 1;
    res = (res << 1) | bit;
  }
  return res >>> 0; // bitwise ops yield int32, convert back to unsigned
};

190_solution2_divideAndConquer.js

// Swap the two 16-bit halves.
// Within each half, swap the 8-bit halves.
// Then swap 4-bit groups, then 2-bit groups, then single bits
/**
 * @param {number} n - a positive integer
 * @return {number} - a positive integer
 */
var reverseBits = function (n) {
  let x = n;
  x = (x >>> 16) | (x << 16);
  x = ((x & 0xff00ff00) >>> 8) | ((x & 0x00ff00ff) << 8);
  x = ((x & 0xf0f0f0f0) >>> 4) | ((x & 0x0f0f0f0f) << 4);
  x = ((x & 0xcccccccc) >>> 2) | ((x & 0x33333333) << 2);
  x = ((x & 0xaaaaaaaa) >>> 1) | ((x & 0x55555555) << 1);
  return x >>> 0; // bitwise ops yield int32, convert back to unsigned
};

190_solution1_sequential.py

class Solution:
    def reverseBits(self, n: int) -> int:
        res = 0
        for i in range(32):
            bit = (n >> i) & 1
            res = (res << 1) | bit
        return res

190_solution2_divideAndConquer.py

# Swap the two 16-bit halves.
# Within each half, swap the 8-bit halves.
# Then swap 4-bit groups, then 2-bit groups, then single bits
class Solution:
    def reverseBits(self, n: int) -> int:
        M = 0xFFFFFFFF  # optional: the 8-bit swap masks below already drop bits above 31
        x = n
        x = ((x >> 16) | (x << 16)) & M
        x = ((x & 0xFF00FF00) >> 8) | ((x & 0x00FF00FF) << 8)
        x = ((x & 0xF0F0F0F0) >> 4) | ((x & 0x0F0F0F0F) << 4)
        x = ((x & 0xCCCCCCCC) >> 2) | ((x & 0x33333333) << 2)
        x = ((x & 0xAAAAAAAA) >> 1) | ((x & 0x55555555) << 1)
        return x

190_solution1_sequential.rs

impl Solution {
    pub fn reverse_bits(x: u32) -> u32 {
        let mut res = 0;
        for i in 0..32 {
            let bit = (x >> i) & 1;
            res = (res << 1) | bit;
        }
        res
    }
}

190_solution2_divideAndConquer.rs

// Swap the two 16-bit halves.
// Within each half, swap the 8-bit halves.
// Then swap 4-bit groups, then 2-bit groups, then single bits
impl Solution {
    pub fn reverse_bits(mut x: u32) -> u32 {
        x = (x >> 16) | (x << 16);
        x = ((x & 0xFF00FF00) >> 8) | ((x & 0x00FF00FF) << 8);
        x = ((x & 0xF0F0F0F0) >> 4) | ((x & 0x0F0F0F0F) << 4);
        x = ((x & 0xCCCCCCCC) >> 2) | ((x & 0x33333333) << 2);
        x = ((x & 0xAAAAAAAA) >> 1) | ((x & 0x55555555) << 1);
        x
    }
}