Bitwise Operator

Introduction

I do not ever retain information so thought I would write this down for next time I forget

Two's Compliment

This is a mysterious word, but like decimal is a way to store numbers, Two's Compliment is a way to signed integers.

In this system we

• Take the binary for +N
• Invert all bits
• Add 1

So here is an example
Step 1: +10

0000000000001010

Step 2: Invert

1111111111110101

Step 3: add 1

1111111111110101
              +1
----------------
1111111111110110

Signed vs Unsigned Values

Bits by themselves have no meaning. A sequence like:

 11101000

is just eight bits. The type that holds those bits decides how they are interpreted.

Unsigned Types

Unsigned types treat the bits as a positive integer.

Example (8‑bit):

 11101000 = 232

Unsigned values never represent negative numbers.

Signed Types

Signed types use the most significant bit (MSB left hand side) as a sign indicator using two's complement.

Example (8‑bit):

 11101000 = −24

The bit pattern is the same as the unsigned example, but the type interprets it differently.

Why This Matters for Bitwise Operations

Right‑shift behaviour depends on whether the value is signed or unsigned:

• Signed types use an arithmetic right shift (>>), which preserves the sign bit.
• Unsigned types use a logical right shift (>>), which always shifts in zeros.
• Some languages provide logical right shift explicitly (>>>), which always shifts in zeros regardless of sign.

Key Idea

Bits are not inherently signed or unsigned. The type determines how the bits are interpreted and how operators behave.

Bitwise Operations Overview

Bitwise operations fall into three major groups:

1. Bitwise Logic Operators
2. Bitwise Shift Operators
3. Bit Rotation Operators

These operations work directly on the binary representation of integers.

1. Bitwise Logic Operators

AND ( & )

A result bit is 1 only if both input bits are 1.

0b1100 & 0b1010 = 0b1000

OR ( | )

A result bit is 1 if either input bit is 1.

0b1100 | 0b1010 = 0b1110

XOR ( ^ )

A result bit is 1 if the input bits are different. A result bit is 0 if the input bits are the same.

0b1100 ^ 0b1010 = 0b0110

NOT ( ~ or ! )

1 becomes 0, and 0 becomes 1.

~0b00001111 = 0b11110000

2. Bitwise Shift Operators

Bitwise shifts move bits left or right. The important difference is what gets inserted into the leftmost bit when shifting right.

(Arithmetic) Left Shift ( << )

Shifts all bits to the left by n positions. Zeros are always shifted in from the right.

Example:

 0001 << 2 = 0100

This is equivalent to multiplying by 2ⁿ for unsigned values.

(Arithmetic) Right Shift ( >> )

Shifts all bits to the right by n positions. The new leftmost bit is filled with the original MSB (the sign bit).

• If the value is positive (MSB = 0), zeros are shifted in.
• If the value is negative (MSB = 1), ones are shifted in.

This preserves the sign of the number.

Example (signed):

 1110 1000 >> 3 = 1111 0100

Logical Right Shift ( >>> )

Shifts all bits to the right by n positions. The new leftmost bit is always 0, regardless of sign.

This treats the value as an unsigned bit pattern.

Example:

 1110 1000 >>> 3 = 0001 1101

Only available in TypeScript/JavaScript.

Logical Right Shift in C and C++

C and C++ do not provide a dedicated logical right shift operator for signed values. The operator >> performs an arithmetic right shift on signed types and a logical right shift on unsigned types.

To force a logical right shift, cast the value to an unsigned type:

 int i = -10;
 unsigned x = (unsigned)i >> 1;

Casting to unsigned causes >> to treat the bits as an unsigned integer, so zeros are shifted in from the left.

Without the cast, >> performs an arithmetic shift and preserves the sign bit:

 int x = i >> 1;   // arithmetic shift, sign bit copied

Wanted to make logical shift really clear to wrote

#include <iostream>
#include <bitset>

using namespace std;

int main() {
    int i = -10;

    cout << "i dec : " << i << endl;
    cout << "i bin : " << bitset<32>(i) << endl;

    int y = i >> 1;

    cout << "\nC++ Arithmetic right shift" << endl;
    cout << "y dec : " << y << endl;
    cout << "y bin : " << bitset<32>(y) << endl;

    unsigned x = (unsigned)i >> 1;

    cout << "\nFake C++ logical right shift to unsigned" << endl;
    cout << "x dec : " << x << endl;
    cout << "x bin : " << bitset<32>(x) << endl;
}

And the output was i dec : -10 i bin : 11111111111111111111111111110110

C++ Arithmetic right shift y dec : -5 y bin : 11111111111111111111111111111011

Fake C++ logical right shift to unsigned x dec : 2147483643 x bin : 01111111111111111111111111111011

3. Bit Rotation Operators

Bit rotation moves bits around in a loop. Bits that fall off one end are wrapped around to the other end *in the same order they fell off*.

Rotate Left (ROL)

ROL(0b1001, 1) = 0b0011

(the leftmost bit '1' drops off and reappears on the right)

Rotate Right (ROR)

ROR(0b1001, 1) = 0b1100

(the rightmost bit '1' drops off and reappears on the left)

Ordering rule: If multiple bits drop off, they are placed on the opposite end in the same order. Example:

 ROR(0b1110, 2)
 rightmost bits '10' drop off → reappear on the left as '10'
 result = 0b1011

Note: Rust, C# (BitOperations), and C++20 (std::rotl/rotr) provide built‑in rotate functions.

Rotation Operator Usage

So during my noting of my ruined brain, I came up on this.

hash = (hash ^ value).rotate_left(5) * 0x9E3779B9

I was asking about the use of rotate to the robot. And the only one I could think of was circular buffers as I had used these in light displays on microcontrollers. So wanted to dig a little deeper. So hear goes. I want to break it down so even someone as stupid as me can understand. Should be a challenge. So apparently this is a mixing function - first google on my trip. So I think this just means something that mixes data using a formula
Its job is to take two inputs (hash and value) and produce a new hash that:

• spreads bits out
• avoids collisions
• avoids patterns
• preserves entropy
• is fast on real hardware

So basically this function

• hash ^ value XOR combines the new data - cheap, reversible,
• .rotate_left(5), no data loss, spreads data across positions, cheap
• * 0x9E3779B9, multiplies by magic number

Language Support Table

Operation	Rust	C	C++	C#	TypeScript
AND ( & )	✔	✔	✔	✔	✔
)	✔	✔	✔	✔	✔
XOR ( ^ )	✔	✔	✔	✔	✔
NOT ( ~ / ! )	! for ints	~	~	~	~
Left Shift ( << )	✔	✔	✔	✔	✔
Right Shift ( >> )	✔	✔	✔	✔	✔
Logical Right Shift ( >>> )	✘	✘	✘	✘	✔
Rotate Left	rotate_left()	✘	std::rotl	RotateLeft	✘
Rotate Right	rotate_right()	✘	std::rotr	RotateRight	✘

Language Notes

Rust

• Right shift is arithmetic for signed integers, logical for unsigned.
• Bitwise NOT uses ! instead of ~.
• Provides built‑in rotate_left() and rotate_right().

C

• Right shift of signed integers is implementation-defined.
• No built‑in rotate operations.

C++

• C++20 adds std::rotl and std::rotr.
• Right shift of signed integers is implementation-defined (same as C).

C#

• Right shift is arithmetic for signed, logical for unsigned.
• Provides BitOperations.RotateLeft/Right.

TypeScript

• Has both arithmetic (>>) and logical (>>>) right shift.
• No built‑in rotate; must be implemented manually.