Skip to content
Tutorials Center
My learning

Topics

Lesson 94 of 132 ยท Standard Library Tour

Bit Manipulation and Integer Tricks

Learn bit manipulation in Rust: shifts, masks, set and clear bits, count_ones, leading_zeros, rotate, bit packing and building bitflags by hand.

Every integer in your computer is a row of bits, and Rust gives you precise, safe tools for working with them directly. Bit manipulation shows up in more places than you might expect: file formats and network protocols pack several fields into one byte, permission systems store a dozen yes/no settings in one number, hash functions and random number generators are built from shifts and XORs, and a u64 can serve as a set of 64 small integers that is checked in a single instruction.

This lesson covers the operators (&, |, ^, !, <<, >>), how shifts behave for signed and unsigned types, the helper methods the standard library gives every integer (count_ones, leading_zeros, rotate_left and friends), the classic one-line tricks, and finally a flag type built by hand, which is what the popular bitflags crate generates for you. If you need a refresher on the integer types themselves, see Scalar Types and Numeric Conversion; overflow rules are in Integer Overflow.

Bitwise operators and formatting

The operators work on every bit position independently:

Operator Name Result bit is 1 when...
a & b AND both bits are 1
a | b OR at least one bit is 1
a ^ b XOR the bits differ
!a NOT the bit is 0 (flips every bit)
a << n shift left moves bits toward the high end, filling with 0
a >> n shift right moves bits toward the low end

Each has a compound form (&=, |=, ^=, <<=, >>=). To see bits, format with {:b} (binary), {:o} (octal), {:x} (hex) and the flags # (add the 0b/0x prefix), 0 (pad with zeros) and a width: {:#010b} prints a u8 such as 0b00001011. Underscores in literals (0b0000_1011) are only for readability.

Shifting right behaves differently depending on the type. For unsigned integers the new high bits are zeros (a logical shift). For signed integers the sign bit is copied (an arithmetic shift), so a negative number stays negative: -16i8 >> 2 is -4. Shifting left by n multiplies by 2^n as long as no set bit falls off the top, and shifting right by n divides by 2^n, rounding toward negative infinity.

Rust Shifts, signed and unsigned

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with io::stdin().read_line()), it gets the next line from this box.

A shift by the type's width or more (for example x << 8 on a u8) is an error: the compiler rejects it when the amount is a constant, and a debug build panics at run time otherwise. Use checked_shl/checked_shr to get None instead, or wrapping_shl/wrapping_shr, which reduce the amount modulo the width. Note that !x on an unsigned type flips only the bits of that type, while for signed types !x equals -x - 1.

Setting, clearing, toggling and testing bits

Bit n (counting from 0 at the right) has the value 1 << n. A mask is a number with 1s in the positions you care about. Four operations cover most needs:

Goal Code
Set bit n x |= 1 << n
Clear bit n x &= !(1 << n)
Toggle bit n x ^= 1 << n
Test bit n x & (1 << n) != 0

To pull out a multi-bit field, shift it down and mask it: (x >> shift) & mask. To write a field, clear its old bits first, then OR in the new value shifted into place. This is how a date can be packed into 16 bits (7 for the year since 2000, 4 for the month, 5 for the day):

flowchart LR
    V["u16 packed value"] --> Y["year: (v >> 9) & 0x7F"]
    V --> M["month: (v >> 5) & 0xF"]
    V --> D["day: v & 0x1F"]

Each field is extracted with a shift and a mask; packing is the reverse.

Rust Packing a date into 16 bits

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with io::stdin().read_line()), it gets the next line from this box.

Counting, scanning and rotating

Every integer type has methods that map directly onto CPU instructions, so they are much faster than any loop you could write by hand:

  • count_ones() and count_zeros() count set and unset bits (the population count, or popcount).
  • leading_zeros() and trailing_zeros() count zeros from the high or low end. For a value of 0 they return the full bit width.
  • ilog2() is the position of the highest set bit (it panics on 0; checked_ilog2 returns None).
  • rotate_left(n) and rotate_right(n) shift bits around the ends instead of losing them.
  • reverse_bits() mirrors the bit order; swap_bytes() reverses byte order (endianness conversion).
  • is_power_of_two() and next_power_of_two() on unsigned types.
  • to_be_bytes(), to_le_bytes() and from_be_bytes()/from_le_bytes() convert between integers and byte arrays in a chosen byte order.
Rust Counting and one-line tricks

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with io::stdin().read_line()), it gets the next line from this box.

The tricks all follow from one observation: subtracting 1 from a number flips the lowest set bit to 0 and every zero below it to 1, so x & (x - 1) removes the lowest set bit, and x & -x (written x.wrapping_neg() for unsigned types) isolates it. A number is a power of two exactly when it has a single set bit. In real code prefer is_power_of_two() and count_ones(); the manual forms are worth knowing because you will meet them in other people's code.

Arithmetic on small types overflows long before you expect. In a debug build 200u8 + 100 panics; in release it wraps. When you mean to wrap (hashes, checksums), say so with wrapping_add, wrapping_mul and friends. Never rely on the debug/release difference.

A bit set in one integer

A u64 is a set of the numbers 0 to 63: bit i is 1 when i is a member. Union is |, intersection is &, difference is a & !b, size is count_ones() and membership is a single AND. Iterating the members uses trailing_zeros() plus "clear the lowest bit":

Rust
let mut rest = set;
while rest != 0 {
    let member = rest.trailing_zeros();
    rest &= rest - 1;
}

The same idea scales to larger sets by using an array of u64 words, which is how the bitvec-style crates and many compilers store dense sets.

Building flags by hand

An operating system call may take options like read, write and execute. Passing three bools is clumsy; passing one small integer whose bits are the options is compact and easy to extend. The bitflags crate generates this boilerplate. Here it is written out, so you know exactly what it does: a newtype over u8, one associated constant per flag, the bit operators implemented through the std::ops traits, and a few helper methods.

Rust A Permissions type like bitflags

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with io::stdin().read_line()), it gets the next line from this box.

Notice what the newtype buys you: Permissions::READ | Permissions::EXEC cannot be confused with an arbitrary number, contains documents intent, and the Debug output lists names instead of bits. Because the type is Copy and wraps a single u8, it costs exactly one byte. When you need more than a handful of flags, a serialization format, or a Display and parsing implementation, switching to the bitflags crate saves boilerplate, but the semantics are the ones shown here.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. What is -16i8 >> 2 in Rust?

    Right shifts on signed integers are arithmetic: the sign bit is copied into the vacated positions, so the result is -4. Reading the same bits as a u8 would give 60.
  2. 2. Which expression clears bit n of x and leaves the others alone?

    !(1 << n) is a mask with every bit set except bit n, so ANDing with it clears only that bit. |= sets it, ^= toggles it, and &= (1 << n) would keep only that bit.
  3. 3. What does x & (x - 1) compute for an unsigned x that is not zero?

    Subtracting 1 turns the lowest set bit into 0 and the zeros below it into 1s. ANDing with the original removes that lowest set bit. x & x.wrapping_neg() isolates it instead.
  4. 4. Why does the example write Permissions(!self.0 & Permissions::ALL.0) in its Not implementation?

    !self.0 flips all eight bits, including five that no flag uses. Masking with ALL keeps the value inside the set of valid flags.

Summary

  • &, |, ^, !, << and >> work bit by bit; format with {:b}, {:x} and {:#010b} to see the bits.
  • Right shift is logical for unsigned and arithmetic for signed types; shifting by the bit width or more is an error, so use checked_shl or wrapping_shl for variable amounts.
  • Set with |=, clear with &= !mask, toggle with ^=, test with & mask != 0; extract fields with (x >> shift) & mask.
  • Use count_ones, leading_zeros, trailing_zeros, ilog2, rotate_left, reverse_bits, swap_bytes and to_be_bytes instead of hand-written loops.
  • x & (x - 1) clears the lowest set bit; x & x.wrapping_neg() isolates it.
  • A u64 can hold a small set; a newtype with associated constants and operator traits is the shape of a flags type, and the bitflags crate automates it.

Next: Testing in Rust