Why does x & (x - 1) determine whether a number is a power of two?

A positive integer is a power of two if and only if its binary representation has exactly one '1' bit (e.g., 8 is 00001000). Subtracting 1 inverts that single set bit and sets all lower trailing zeros to 1 (8 - 1 = 7 is 00000111). Performing a bitwise AND between x and x-1 yields 0. For any other number with multiple set bits, the highest set bit remains untouched, yielding a non-zero result.

How does the XOR variable swap trick work without temporary memory?

The algorithm executes three steps: 1) a = a ^ b; 2) b = a ^ b; 3) a = a ^ b. Because XOR is commutative, associative, and its own inverse (x ^ x = 0 and x ^ 0 = x), substituting step 1 into step 2 gives b = (a_orig ^ b_orig) ^ b_orig = a_orig. Substituting into step 3 gives a = (a_orig ^ b_orig) ^ a_orig = b_orig, swapping both variables.

What is the difference between an arithmetic right shift and a logical right shift?

A logical right shift always fills the newly created leftmost vacant bit positions with zeros (0). An arithmetic right shift preserves the sign bit (MSB) by replicating the original sign bit (0 for positive, 1 for negative), ensuring correct division by powers of two for signed negative numbers.

Computer Science • Beginner • 20 minutes

Binary & Bitwise Operations Studio Sandbox

Master the foundational binary language of computing. Toggle individual bits on interactive 8-bit register tiles, evaluate parallel Boolean logic gates (AND, OR, XOR, NOT, NAND, NOR, XNOR), perform bit shifts and circular rotations, convert Two's complement negative integers, and execute high-speed bit twiddling hacks.

Launch Interactive Lab

Telemetry Cockpit Live Simulator

Target Objectives

Trace logic flow and algorithm behavior step by step.
Measure performance and complexity trade-offs.
Experiment with structures and systems in a safe sandbox.

Framework: HTML5 / WebGLOpenLabs Sandbox

Theory & Core Foundations

Bitwise Operations are primitive low-level operations that manipulate individual binary digits (bits: 0 or 1) at the hardware register level. In digital computers, data is represented in binary format where each bit represents a power of two ($2^0, 2^1, \dots, 2^7$ in an 8-bit byte, with values ranging from $0$ to $255$ unsigned).

Core bitwise primitives include:

AND (&): Yields 1 if and only if both input bits are 1; used for bit masking (extracting specific bit fields).
OR (|): Yields 1 if either input bit is 1; used for setting bits to 1.
XOR (^): Yields 1 if input bits differ; used for toggling bits, parity generation, and cryptographic stream ciphers.
NOT (~): Inverts every bit (one's complement).
Bit Shifts (<<, >>): Left shift ($x \ll n$) multiplies by $2^n$; Logical Right shift ($x \gg n$) divides by $2^n$.

Signed integers are represented using Two's Complement, where the Most Significant Bit (MSB, bit 7) serves as the sign bit with negative positional weight ($-2^7 = -128$), enabling negative and positive arithmetic addition with identical hardware circuitry.

Mathematical Foundations

Two's complement avoids the ambiguity of dual zeros (+0 and -0) found in sign-magnitude representations and allows standard binary adders to compute subtractions directly as A - B = A + (~B + 1).

x \ll n = x \times 2^n \pmod{256}

x \gg n = \lfloor x / 2^n \rfloor

-x = \sim x + 1 \text{ (Two's Complement Negation)}

\text{Signed Value} = -b_7 \cdot 2^7 + \sum_{i=0}^{6} b_i \cdot 2^i

\text{Lowest Set Bit} = x \,\&\, (-x)

How The Simulation Works

Click individual bit buttons on Register A and Register B to toggle their states (0 or 1). Select any logic operator (AND, OR, XOR, NOT, NAND, NOR, XNOR, SHL, SHR, ROL, ROR) to watch the result compute instantaneously. Toggle Signed Mode to inspect Two's complement interpretations, or browse the Bit Hacks tab to test famous bit manipulation algorithms.

Knowledge Graph & Related Concepts

Related Experiments & Simulations

HTML/CSS/JS Editor

Live web code editor

JS Event Loop Visualizer

Interactive JavaScript event loop visualizer

CPU Micro-Architecture & 8-Bit Assembly

8-bit assembly editor, 4-stage instruction cycle, datapath bus animation, and register file

Binary & Bitwise Operations Studio

Interactive 8-bit register tiles, bitwise logic gates, shifts, rotations, Two's complement, and mask hacks

Frequently Asked Questions

Learning Objectives

•Construct truth tables and compute outputs for all fundamental Boolean bitwise operators (AND, OR, XOR, NOT, NAND, NOR, XNOR).
•Calculate integer multiplication and division using bitwise left shift (<<) and right shift (>>).
•Perform Two's complement negation (~x + 1) and determine signed decimal values (-128 to +127).
•Apply bit twiddling algorithms (e.g. isolating lowest set bit x & -x, checking power of two x & (x - 1) == 0, XOR swap without temporary storage).

Real World Applications

✓Computer Graphics & Alpha Masking: Extracting RGBA color channels (Red = (pixel >> 24) & 0xFF) and fast bitmask sprite collision detection.
✓Network Engineering & Subnetting: Applying IPv4 subnet masks (e.g. IP & 255.255.255.0) to isolate network and host addresses.
✓Cryptography & Hashing: High-speed bitwise rotations and XOR operations forming the core rounds of AES, SHA-256, and ChaCha20.
✓Data Compression: Huffman encoding and bit-packing arrays to minimize memory footprint in high-frequency trading engines.