Ch2.17: Bit operations and <bit> header

Bits explained

A bit is a binary digit: either 0 or 1. In an unsigned integer, each bit position represents a power of 2.

Bit position:   7   6   5   4   3   2   1   0
Power of two: 128  64  32  16   8   4   2   1
Binary value:   0   1   0   0   1   0   1   1
Decimal sum = 64 + 8 + 2 + 1 = 75
      

Do not confuse bitwise with logical

Bitwise operators (&, |, ^, ~) operate on individual bits of integers. Logical operators (&&, ||, !) operate on boolean values and return true/false. For example, a & b combines bits; a && b checks if both are nonzero.

Operation summary table

The table shows what each operator does and example results (with binary using fast_io::bin<true,true>).

Bitwise operators with binary output

Use fast_io::bin<true,true> to print a value’s binary with 0b prefix and zero padding.

#include <fast_io.h>

int main() {
    using namespace ::fast_io::iomnp;

    unsigned a{0b1010u}; // 10, 0b00001010
    unsigned b{0b1100u}; // 12, 0b00001100

    println("a = ", a, " ", bin<true,true>(a)); 
    // a = 10 0b00001010

    println("b = ", b, " ", bin<true,true>(b)); 
    // b = 12 0b00001100

    auto andv{a & b};
    println("a & b = ", andv, " ", bin<true,true>(andv)); 
    // a & b = 8 0b00001000

    auto orv{a | b};
    println("a | b = ", orv, " ", bin<true,true>(orv)); 
    // a | b = 14 0b00001110

    auto xorv{a ^ b};
    println("a ^ b = ", xorv, " ", bin<true,true>(xorv)); 
    // a ^ b = 6 0b00000110

    auto notv{~a};
    println("~a = ", notv, " ", bin<true,true>(notv)); 
    // ~a = (platform-dependent). For 32-bit unsigned: 4294967285 0b11111111111111111111111111110101

    auto lshift{a << 1};
    println("a << 1 = ", lshift, " ", bin<true,true>(lshift)); 
    // a << 1 = 20 0b00010100

    auto rshift{b >> 2};
    println("b >> 2 = ", rshift, " ", bin<true,true>(rshift)); 
    // b >> 2 = 3 0b00000011
}

Shift intuition (ASCII diagram)

Start:             0 b 0 0 0 0 1 0 1 0   (= 10)
Left shift by 1 →  0 b 0 0 0 1 0 1 0 0   (= 20)

Start:             0 b 0 0 0 0 1 1 0 0   (= 12)
Right shift by 2 → 0 b 0 0 0 0 0 0 1 1   (= 3)
      

Left shift moves bits left (fills right with 0); right shift moves bits right (fills left with 0 for unsigned).

<bit> header utilities

The <bit> header provides tools for analyzing and transforming bit patterns. See cppreference: cppreference: <bit> header.

• ::std::popcount(x): number of set (1) bits.
• ::std::countl_zero(x): leading zeros (depends on width).
• ::std::countr_zero(x): trailing zeros.
• ::std::rotl(x, s): rotate left by s bits.
• ::std::rotr(x, s): rotate right by s bits.
• ::std::bit_width(x): number of bits needed to represent x.

#include <fast_io.h>
#include <bit>

int main() {
    using namespace ::fast_io::iomnp;

    unsigned x{0b101100u}; // 44, 0b00101100

    println("x = ", x, " ", bin<true,true>(x)); 
    // x = 44 0b00101100

    println("popcount = ", ::std::popcount(x)); 
    // popcount = 3

    println("countl_zero = ", ::std::countl_zero(x)); 
    // countl_zero = (depends on width; e.g., 26 for 32-bit unsigned)

    println("countr_zero = ", ::std::countr_zero(x)); 
    // countr_zero = 2

    auto rotl2{::std::rotl(x,2)};
    println("rotl(x,2) = ", rotl2, " ", bin<true,true>(rotl2)); 
    // rotl(x,2) = 176 0b10110000

    auto rotr2{::std::rotr(x,2)};
    println("rotr(x,2) = ", rotr2, " ", bin<true,true>(rotr2)); 
    // rotr(x,2) = 11 0b00001011

    println("bit_width = ", ::std::bit_width(x)); 
    // bit_width = 6 (needs 6 bits to represent 44)
}

Key takeaways

• Binary insight: Print with fast_io::bin<true,true> to see bit changes.
• Bitwise vs logical: Do not confuse &/| with &&/||.
• Operators: AND, OR, XOR, NOT, shifts manipulate bit patterns; shifts insert zeros for unsigned.
• Utilities: Use <bit> functions for counting, shifting via rotation, and measuring width.