Bitwise operations

Operators

Operator	Name	Logic	Resulting Bit is 1 if
&	AND	a & b	both bits are 1.
|	OR	a | b	at least one bit is 1.
^	XOR	a ^ b	the bits are different.
~	NOT	~a	the input bit is 0 (it flips the bit).
<<	Left Shift	a << n	Shifts bits to the left adding 0s to the right.
>>	Right Shift	a >> n	Shifts bits to the right discarding bits on the right.

Powers of two

If you're working in powers of two you can make use of bitwise operations to avoid expensive modulus and division operations

This works only if n is a power of two

#include <bit>

// Suppose we want to multiply/divide/modulo by 16
constexpr uint64_t N = 16;       // The power of two value

static_assert(std::has_single_bit(N), "N must be a power of two");

template <uint64_t T>
concept PowerOfTwo = requires (T n) {
  std::has_single_bit(n);
};

// divide: a / N
uint64_t divide(uint64_t a)
{
  return a >> std::countr_zero(N);
}

// multiply: a * N
uint64_t multiply(uint64_t a)
{
  return a << std::countr_zero(N);
}

// modulus: a % N
uint64_t modulus(uint64_t a)
{
  return a & (N - 1);
}

// Get the next multiple of n
template <uint64_t N>
requires PowerOfTwo<N>
uint64_t nextMultipleOf(uint64_t value)
{
  return (value + N - 1) & ~(N - 1);
}

Operation	Standard Arithmetic	Bitwise Equivalent	Logic
Divide	a / 2^n	a >> n	Shifting right n times is mathematically identical to floor division by 2n.
Multiply	a * 2^n	a << n	Shifting left n times adds zeros
Modulus	a % 2^n	a & (2^n - 1)	Masking with 2n−1 keeps only the remainder bits.

Useful bitwise operations

Turn on a bit

void on(uint64_t &mask, uint32_t n)
{
  mask |= 1ULL << n;
}

Turn off a bit

void off(uint64_t &mask, uint32_t n)
{
  mask &= ~(1ULL << n);
}

Toggle a bit

void toggle(uint64_t &mask, uint32_t n)
{
  mask ^= 1ULL << n;
}

Check if a bit is on

bool isOn(uint64_t mask, uint32_t n)
{
  return (mask & (1ULL << n)) != 0;
}

Check if an unsigned int is odd

If the LSB is on, the number is odd, otherwise it's even.

bool isOdd(uint64_t mask, uint32_t n)
{
  return (mask & 1ULL) == 1;
}

Notice how I used 1ULL, it's because I use a 64 bit unsigned integer as the mask.

Check if an unsigned int is a power of two

#include <bit> // C++20 bitwise operations

bool isPowerOfTwo(uint64_t a)
{
  // return a > 0 && (a & (a - 1)) == 0; // Before C++20
  return std::has_single_bit(a);         // C++20
}