Bit Manipulation Algorithms

Overview

Bit manipulation algorithms operate directly on binary representations of numbers, using bitwise operators to perform computations at the bit level. These algorithms form the foundation for low-level optimizations, compression techniques, cryptographic operations, and systems programming tasks where direct control over individual bits provides performance advantages or specific functionality requirements.

The fundamental concept involves treating integers as sequences of bits rather than abstract numeric values. Each bit position represents a power of two, and operations can set, clear, toggle, or test individual bits or groups of bits. This direct manipulation bypasses higher-level arithmetic operations, often resulting in faster execution and more compact code.

Bit manipulation algorithms appear throughout computing systems. Network protocols use bit masking to extract packet headers. Graphics systems manipulate pixel data at the bit level for color operations. Database systems use bitmap indexes for query optimization. Embedded systems rely on bit manipulation to control hardware registers with minimal overhead.

# Binary representation of 13
number = 13
# => 0b1101 (binary: 1101)

# Check if third bit (0-indexed) is set
bit_set = (number & (1 << 3)) != 0
# => true (bit pattern: 1101, position 3 is 1)

The efficiency gains from bit manipulation stem from direct CPU support for bitwise operations. Modern processors execute bitwise operations in a single clock cycle, making them significantly faster than equivalent arithmetic or logical operations. A bit manipulation approach can replace multiple arithmetic operations with a single bitwise operation, reducing both execution time and code complexity.

Key Principles

Bit manipulation algorithms rely on fundamental bitwise operators that operate on the binary representation of integers. Ruby supports six core bitwise operators inherited from C-style languages.

The AND operator (&) performs a logical AND on corresponding bits. The result bit is 1 only when both input bits are 1. This operation masks specific bits, extracting portions of a binary value while zeroing out unwanted bits. Setting a mask with 1s in positions to preserve and 0s elsewhere, then ANDing with the target value, isolates the desired bits.

# Extract lower 4 bits from a byte
value = 0b11010110
mask = 0b00001111
result = value & mask
# => 0b00000110 (only lower 4 bits preserved)

The OR operator (|) performs a logical OR, producing 1 when either input bit is 1. This operation sets specific bits to 1 while leaving others unchanged. Creating a mask with 1s in positions to set, then ORing with the target value, forces those bits to 1.

The XOR operator (^) produces 1 when bits differ and 0 when they match. XOR serves multiple purposes: toggling bits, swapping values without temporary variables, and detecting differences between binary values. XORing a value with itself produces zero, and XORing with zero leaves the value unchanged.

# Toggle specific bits
value = 0b11010110
toggle_mask = 0b00110000
result = value ^ toggle_mask
# => 0b11100110 (bits at positions 4-5 toggled)

# Swap without temporary variable
a = 5  # 0b0101
b = 3  # 0b0011
a ^= b # a becomes 0b0110
b ^= a # b becomes 0b0101
a ^= b # a becomes 0b0011
# a is now 3, b is now 5

The NOT operator (~) inverts all bits, converting 0 to 1 and 1 to 0. In Ruby, this performs two's complement negation, effectively computing -(n+1). This behavior stems from how Ruby represents negative numbers using two's complement notation.

Left shift (<<) moves bits toward higher positions, filling vacated lower bits with zeros. Each left shift by one position multiplies the value by two. Right shift (>>) moves bits toward lower positions. Ruby provides arithmetic right shift that preserves the sign bit for negative numbers.

# Left shift multiplies by powers of 2
value = 5      # 0b0101
shifted = value << 2  # 0b010100
# => 20 (5 * 2^2)

# Right shift divides by powers of 2
value = 20     # 0b10100
shifted = value >> 2  # 0b101
# => 5 (20 / 2^2)

Bit manipulation algorithms combine these operators to perform complex operations. Setting a specific bit uses OR with a mask containing 1 at that position. Clearing a specific bit uses AND with a mask containing 0 at that position and 1s elsewhere. Testing a bit uses AND with a mask containing 1 at that position, checking if the result is non-zero.

The power of bit manipulation derives from understanding how binary representation relates to position values. The rightmost bit (position 0) represents 2^0 = 1. The next bit (position 1) represents 2^1 = 2. Each position represents twice the value of the position to its right. This positional notation allows algorithms to isolate and manipulate specific value ranges efficiently.

Ruby Implementation

Ruby provides direct access to bitwise operators through standard operators that work on integer values. Unlike languages with fixed-width integer types, Ruby integers grow automatically to accommodate any value, eliminating overflow concerns for most bit manipulation operations.

class BitManipulator
  # Set bit at position to 1
  def self.set_bit(number, position)
    number | (1 << position)
  end

  # Clear bit at position to 0
  def self.clear_bit(number, position)
    number & ~(1 << position)
  end

  # Toggle bit at position
  def self.toggle_bit(number, position)
    number ^ (1 << position)
  end

  # Check if bit at position is set
  def self.check_bit(number, position)
    (number & (1 << position)) != 0
  end
end

value = 0b1010
value = BitManipulator.set_bit(value, 0)
# => 0b1011
value = BitManipulator.clear_bit(value, 3)
# => 0b0011

Ruby's Integer class includes methods that support bit manipulation operations beyond basic operators. The [] operator extracts individual bits, providing cleaner syntax for bit testing. The bit_length method returns the number of bits required to represent the integer, excluding the sign bit.

number = 0b1101

# Extract bit at position using []
bit_2 = number[2]
# => 1

# Get number of significant bits
bits_needed = number.bit_length
# => 4

# Check multiple bit positions
(0...bits_needed).map { |i| number[i] }
# => [1, 0, 1, 1]

Counting set bits (popcount or Hamming weight) determines how many 1 bits appear in the binary representation. The Brian Kernighan algorithm provides an efficient implementation that runs in time proportional to the number of set bits rather than the total number of bits.

def count_set_bits(number)
  count = 0
  while number > 0
    number &= number - 1  # Clear rightmost set bit
    count += 1
  end
  count
end

count_set_bits(0b1011)
# => 3

# Alternative using String conversion
def count_set_bits_alt(number)
  number.to_s(2).count('1')
end

The operation number & (number - 1) clears the rightmost set bit. Subtracting 1 from a number flips all bits after the rightmost set bit, including that bit. ANDing the original with this value eliminates the rightmost 1. Repeating this operation until the number becomes zero counts all set bits.

Checking if a number is a power of two exploits the property that powers of two have exactly one set bit in their binary representation. A power of two ANDed with one less than itself always produces zero, since the single set bit in the power of two gets cleared.

def power_of_two?(number)
  return false if number <= 0
  (number & (number - 1)) == 0
end

power_of_two?(16)  # 0b10000
# => true
power_of_two?(18)  # 0b10010
# => false

Finding the rightmost set bit extracts the position of the lowest 1 bit. The operation number & -number isolates this bit. Negating a number in two's complement flips all bits and adds 1, which causes all trailing zeros to remain zero and the first 1 to stay 1, while clearing all higher bits.

def rightmost_set_bit(number)
  number & -number
end

rightmost_set_bit(0b1011000)
# => 0b1000 (bit at position 3)

def rightmost_set_bit_position(number)
  return -1 if number == 0
  isolated = number & -number
  (isolated.bit_length - 1)
end

rightmost_set_bit_position(0b1011000)
# => 3

Practical Examples

Bitmap-based sets represent collections of integers using individual bits. Each bit position corresponds to a possible element value, with 1 indicating presence and 0 indicating absence. This representation provides constant-time membership testing and set operations using bitwise operators.

class BitSet
  def initialize
    @bits = 0
  end

  def add(element)
    raise ArgumentError, "Element must be non-negative" if element < 0
    @bits |= (1 << element)
  end

  def remove(element)
    @bits &= ~(1 << element)
  end

  def include?(element)
    return false if element < 0
    (@bits & (1 << element)) != 0
  end

  def union(other)
    result = BitSet.new
    result.instance_variable_set(:@bits, @bits | other.instance_variable_get(:@bits))
    result
  end

  def intersection(other)
    result = BitSet.new
    result.instance_variable_set(:@bits, @bits & other.instance_variable_get(:@bits))
    result
  end

  def to_a
    elements = []
    temp = @bits
    position = 0
    while temp > 0
      if (temp & 1) == 1
        elements << position
      end
      temp >>= 1
      position += 1
    end
    elements
  end
end

set1 = BitSet.new
set1.add(1)
set1.add(3)
set1.add(5)
set1.to_a
# => [1, 3, 5]

set2 = BitSet.new
set2.add(3)
set2.add(4)
set2.add(5)

set1.union(set2).to_a
# => [1, 3, 4, 5]
set1.intersection(set2).to_a
# => [3, 5]

Permission systems often encode multiple boolean flags into a single integer. Each bit represents a specific permission, allowing compact storage and efficient permission checking using bitwise operations. This pattern appears in Unix file permissions, database access controls, and application authorization systems.

module Permissions
  READ    = 1 << 0  # 0b001
  WRITE   = 1 << 1  # 0b010
  EXECUTE = 1 << 2  # 0b100
  DELETE  = 1 << 3  # 0b1000
  ADMIN   = 1 << 4  # 0b10000
end

class User
  attr_reader :permissions

  def initialize
    @permissions = 0
  end

  def grant(permission)
    @permissions |= permission
  end

  def revoke(permission)
    @permissions &= ~permission
  end

  def has_permission?(permission)
    (@permissions & permission) == permission
  end

  def has_any_permission?(*perms)
    combined = perms.reduce(0) { |acc, p| acc | p }
    (@permissions & combined) != 0
  end
end

user = User.new
user.grant(Permissions::READ | Permissions::WRITE)
user.has_permission?(Permissions::READ)
# => true
user.has_permission?(Permissions::EXECUTE)
# => false
user.has_any_permission?(Permissions::EXECUTE, Permissions::WRITE)
# => true

Extracting and modifying bit ranges handles structured binary data where multiple fields pack into fixed-width values. Network protocols, file formats, and hardware registers use this pattern to maximize space efficiency.

class BitField
  def initialize(value = 0)
    @value = value
  end

  # Extract bits from start position with given length
  def extract(start, length)
    mask = (1 << length) - 1
    (@value >> start) & mask
  end

  # Set bits at start position with given length to new value
  def set_field(start, length, new_value)
    mask = (1 << length) - 1
    # Clear the field
    @value &= ~(mask << start)
    # Set the new value
    @value |= ((new_value & mask) << start)
  end

  def to_i
    @value
  end
end

# Example: RGB color packed into 24 bits
# Format: RRRRRRRRGGGGGGGGBBBBBBBB
color = BitField.new(0xFF8040)

red = color.extract(16, 8)
# => 255
green = color.extract(8, 8)
# => 128
blue = color.extract(0, 8)
# => 64

color.set_field(8, 8, 200)  # Change green component
color.to_i.to_s(16)
# => "ffc840"

Finding the next power of two greater than or equal to a given number supports memory allocation and buffer sizing. The algorithm sets all bits after the highest set bit to 1, then adds 1 to round up.

def next_power_of_two(number)
  return 1 if number <= 0
  return number if (number & (number - 1)) == 0  # Already power of 2

  # Set all bits after highest set bit
  number -= 1
  number |= number >> 1
  number |= number >> 2
  number |= number >> 4
  number |= number >> 8
  number |= number >> 16
  number |= number >> 32
  number + 1
end

next_power_of_two(100)
# => 128
next_power_of_two(64)
# => 64
next_power_of_two(65)
# => 128

Common Patterns

The single bit mask pattern creates masks for individual bit positions. Rather than hardcoding binary literals, shifting 1 by the position value generates the appropriate mask dynamically. This pattern appears in all bit manipulation operations that target specific positions.

# Create mask for bit position
def bit_mask(position)
  1 << position
end

# Use masks for multiple operations
position = 5
set_mask = bit_mask(position)
clear_mask = ~bit_mask(position)

value = 0b100000
value |= set_mask      # Set bit 5
value &= clear_mask    # Clear bit 5

The range mask pattern generates masks covering multiple consecutive bits. Creating a mask with N consecutive 1 bits involves shifting 1 left by N positions and subtracting 1. This produces N bits of value 1 starting from position 0.

def range_mask(length)
  (1 << length) - 1
end

# Extract lower 8 bits
value = 0xABCD
lower_byte = value & range_mask(8)
# => 0xCD

# Extract bits 4 through 7
def extract_range(value, start, length)
  (value >> start) & range_mask(length)
end

extract_range(0b11010110, 2, 4)
# => 0b0101

The clear lowest bit pattern repeatedly removes the rightmost set bit. The operation n & (n - 1) appears in algorithms that process each set bit individually or count total set bits. This pattern runs in time proportional to the number of set bits.

def process_each_set_bit(number)
  bits = []
  temp = number
  while temp > 0
    rightmost = temp & -temp  # Isolate rightmost bit
    bits << Math.log2(rightmost).to_i  # Get position
    temp &= temp - 1  # Clear rightmost bit
  end
  bits
end

process_each_set_bit(0b10110)
# => [1, 2, 4]

The XOR accumulator pattern detects duplicates or finds unique elements. XORing all elements together causes pairs to cancel out, leaving unpaired elements. This pattern solves the classic "find the unique element" problem when exactly one element appears an odd number of times.

def find_unique_element(array)
  array.reduce(0) { |acc, n| acc ^ n }
end

find_unique_element([4, 2, 4, 5, 2])
# => 5

# Find two unique elements when all others appear twice
def find_two_unique(array)
  xor_all = array.reduce(0) { |acc, n| acc ^ n }
  
  # Find a bit position where the two numbers differ
  rightmost_bit = xor_all & -xor_all
  
  # Partition into two groups and XOR each group
  group1 = group2 = 0
  array.each do |n|
    if (n & rightmost_bit) != 0
      group1 ^= n
    else
      group2 ^= n
    end
  end
  
  [group1, group2]
end

find_two_unique([4, 2, 4, 5, 2, 7])
# => [5, 7]

The bit counting pattern appears in various forms across algorithms. Beyond the Brian Kernighan algorithm, lookup table approaches precompute counts for small ranges and combine results for larger numbers.

# Build lookup table for 8-bit counts
BIT_COUNT_TABLE = (0..255).map { |i| i.to_s(2).count('1') }

def count_bits_fast(number)
  count = 0
  while number > 0
    count += BIT_COUNT_TABLE[number & 0xFF]
    number >>= 8
  end
  count
end

The sign extraction pattern determines if a number is positive, negative, or zero using bit operations. The sign bit (highest bit) indicates negativity in two's complement representation.

def sign(number)
  return 0 if number == 0
  # Right shift by word size minus 1 to move sign bit to LSB
  # Ruby integers are variable width, so use comparison instead
  number >> (number.bit_length)
end

# More portable sign extraction
def sign_portable(number)
  return 0 if number.zero?
  number.positive? ? 1 : -1
end

Performance Considerations

Bit manipulation operations execute as single CPU instructions, providing substantial performance advantages over equivalent arithmetic or logical operations. Modern processors complete bitwise AND, OR, XOR, and shift operations in one clock cycle, while arithmetic operations may require multiple cycles or pipeline stages.

require 'benchmark'

# Compare bit manipulation vs arithmetic for power of 2 check
n = 1_000_000

Benchmark.bm(20) do |x|
  x.report("Bit manipulation:") do
    n.times { |i| (i & (i - 1)) == 0 }
  end
  
  x.report("Math.log2:") do
    n.times { |i| Math.log2(i) % 1 == 0 rescue false }
  end
end

# Bit manipulation typically 10-50x faster

The performance characteristics of bit manipulation algorithms depend on the number of bits processed rather than the magnitude of the values. Counting set bits using Brian Kernighan's algorithm runs in O(k) time where k is the number of set bits, not the number of total bits. For sparse bit patterns, this provides significant advantages over iterating through all bit positions.

Memory access patterns affect bit manipulation performance. Operations on data already in CPU registers complete extremely fast, while loading values from memory introduces latency. Batch processing multiple bit manipulations on the same value amortizes memory access costs across operations.

# Inefficient: Multiple memory accesses
def slow_bit_operations(array)
  array.each do |value|
    check_bit(value, 0)
    check_bit(value, 1)
    check_bit(value, 2)
  end
end

# Efficient: Single load, multiple operations
def fast_bit_operations(array)
  array.each do |value|
    bit0 = (value & 1) != 0
    bit1 = (value & 2) != 0
    bit2 = (value & 4) != 0
    # Process all bits together
  end
end

Branch prediction failures impact performance in bit manipulation code that conditionally executes based on bit values. Modern CPUs predict branch outcomes based on historical patterns. Unpredictable branching on bit values causes pipeline stalls when predictions fail.

# Branch-heavy code prone to misprediction
def process_with_branches(numbers)
  numbers.map do |n|
    if (n & 1) != 0
      n * 2
    else
      n / 2
    end
  end
end

# Branchless using bit manipulation
def process_branchless(numbers)
  numbers.map do |n|
    odd_bit = n & 1
    # Multiply by 2 if odd (left shift), divide by 2 if even (right shift)
    (n << odd_bit) | (n >> (1 - odd_bit))
  end
end

Ruby's arbitrary precision integers introduce overhead for very large numbers. When bit counts exceed the native word size (typically 64 bits), Ruby allocates additional memory and performs multi-precision arithmetic. Keeping values within native integer sizes maximizes performance.

Lookup tables trade memory for speed by precomputing results for common inputs. Bit counting benefits significantly from lookup tables that map 8 or 16-bit values to their bit counts.

# Precompute counts for all 16-bit values
NIBBLE_COUNTS = (0..15).map { |i| i.to_s(2).count('1') }

def count_bits_table(number)
  count = 0
  while number > 0
    count += NIBBLE_COUNTS[number & 0xF]
    number >>= 4
  end
  count
end

Compiler optimizations may transform arithmetic operations into bit manipulations automatically. Multiplication or division by powers of two typically compiles to shift operations. Writing explicit bit manipulations documents intent and ensures the optimization occurs.

Common Pitfalls

Sign extension affects right shift operations on negative numbers. Ruby performs arithmetic right shift, which preserves the sign bit by filling shifted positions with copies of the sign bit. This maintains the value's sign but produces unexpected results when treating integers as unsigned bit patterns.

# Arithmetic right shift on negative number
value = -8  # Binary (two's complement): ...11111000
shifted = value >> 2
# => -2 (Binary: ...11111110, not ...00111110)

# Use bit masking for unsigned-style right shift
def unsigned_right_shift(value, positions)
  mask = (1 << (value.bit_length - positions)) - 1
  (value >> positions) & mask
end

Integer overflow does not occur in Ruby due to automatic bignum promotion, but algorithms designed for fixed-width integers may produce incorrect results when ported directly. Code that relies on overflow wrapping behavior requires explicit modulo operations.

# C-style overflow assumption (incorrect in Ruby)
def increment_with_overflow(byte_value)
  (byte_value + 1) & 0xFF  # Explicit mask needed
end

# Ruby integers grow instead of wrapping
value = 255
value + 1
# => 256 (not 0)

Off-by-one errors plague bit position calculations. Bits numbered from 0 to N-1 for an N-bit number, but intuitive counting starts at 1. Confusion between bit position and bit value causes incorrect mask generation.

# Wrong: Using bit value instead of position
def wrong_set_bit(number, position)
  number | position  # Should be (1 << position)
end

# Correct: Shift 1 to position
def correct_set_bit(number, position)
  number | (1 << position)
end

Negative numbers in two's complement representation have all high-order bits set to 1. Extracting bit ranges from negative numbers without masking includes these sign bits, producing unexpected values.

value = -1  # All bits set to 1
# Attempting to extract lower 8 bits
lower_bits = value & 0xFF
# => 255 (correct with mask)

# Without mask
wrong_extract = value >> 0
# => -1 (sign extension preserves all 1s)

Endianness affects interpretation of multi-byte values as bit sequences. When extracting bits from integers representing packed bytes, the bit numbering depends on whether the most significant byte appears first (big-endian) or last (little-endian).

# Packed as 0xAABBCCDD
value = 0xAABBCCDD

# Extract third byte (different results based on endianness assumption)
third_byte_big_endian = (value >> 8) & 0xFF
# => 0xCC (assuming big-endian bit numbering)

third_byte_little_endian = (value >> 16) & 0xFF
# => 0xBB (assuming little-endian bit numbering)

Bit manipulation on floats requires converting to integer representation. Ruby floats use IEEE 754 format, which encodes sign, exponent, and mantissa as separate bit fields. Extracting these fields requires proper understanding of the floating-point format.

# Cannot directly manipulate float bits in pure Ruby
value = 3.14

# Must pack/unpack to access bit representation
packed = [value].pack('D')
int_bits = packed.unpack1('Q')
# Now can manipulate bits of integer representation

Precedence errors occur when mixing bitwise and comparison operators. Bitwise operators have lower precedence than comparison operators, requiring parentheses to enforce intended evaluation order.

# Wrong precedence
value = 0b1010
if value & 0b0010 != 0  # Parsed as: value & (0b0010 != 0)
  puts "Bit 1 is set"
end

# Correct with parentheses
if (value & 0b0010) != 0
  puts "Bit 1 is set"
end

Reference

Bitwise Operators

Common Bit Manipulation Operations

Common Algorithms

Ruby Integer Methods

Bit Pattern Identities