O.2 — Bitwise operators

The bitwise operators

C++ provides 6 bit manipulation operators, often called bitwise operators:

These are non-modifying operators (they do not modify their operands).

The bitwise operators are defined for integral types and std::bitset. We’ll use std::bitset in our examples because it’s easier to print the output in binary.

Avoid using the bitwise operators with signed integral operands, as many operators will return implementation-defined results prior to C++20 or have other potential gotchas that are easily avoided by using unsigned operands (or std::bitset).

Bitwise left shift (<<) and bitwise right shift (>>) operators

The bitwise left shift (<<) operator shifts bits to the left. The left operand is an expression that provides the initial bit sequence, and the right operand is an integer number that specifies the number of bit-positions to move the bits over by. For example, when we write x << 2, we are saying “produce a value where the bits from x have been moved 2 positions to the left.”

The left operand is not modified, and new bits shifted in from the right size are 0.

Here are some examples of left shifting the bit sequence 0011:

0011 \<\< 1 is 0110
0011 \<\< 2 is 1100
0011 \<\< 3 is 1000

Note that in the third case, we shifted a 1 bit off the end of the number! Bits that are shifted off the end of the bit sequence are lost forever.

The bitwise right shift (>>) operator works similarly but shifts bits to the right.

Here are some examples of right shifting the bit sequence 1100:

1100 />/> 1 is 0110
1100 />/> 2 is 0011
1100 />/> 3 is 0001

Note that in the third case we shifted a bit off the right end of the number, so it is lost.

Let’s do an example in C++ that you can compile and run:

#include <bitset>
#include <iostream>

int main()
{
    std::bitset<4> x { 0b1100 };

    std::cout << x << '\n';
    std::cout << (x >> 1) << '\n'; // shift right by 1, yielding 0110
    std::cout << (x << 1) << '\n'; // shift left by 1, yielding 1000

    return 0;
}

This prints:

1100
0110
1000

What!? Aren’t operator<< and operator>> used for input and output?

They sure are.

Programs today typically do not make much use of the bitwise left and right shift operators to shift bits. Rather, the bitwise left shift operator is more often used with std::cout (or other output stream objects) to output text. Consider the following program:

#include <bitset>
#include <iostream>

int main()
{
    unsigned int x { 0b0100 };
    x = x << 1; // use operator<< for left shift
    std::cout << std::bitset<4>{ x } << '\n'; // use operator<< for output

    return 0;
}

This program prints:

1000

In the above program, how does operator<< know to shift bits in one case and output x in another case? The answer is that it looks at the type of the operands. If the left operand is an integral type, then operator<< knows to do its usual bit-shifting behavior. If the left operand is a an output stream object like std::cout, then it knows it should do output instead.

The same applies for operator>>.

Note that if you’re using operator<< for both output and left shift, parenthesization is required to use for left-shifting:

#include <bitset>
#include <iostream>

int main()
{
	std::bitset<4> x{ 0b0110 };

	std::cout << x << 1 << '\n'; // print value of x (0110), then 1
	std::cout << (x << 1) << '\n'; // print x left shifted by 1 (1100)

	return 0;
}

This prints:

01101
1100

The first line prints the value of x (0110), and then the literal 1. The second line prints the value of x left-shifted by 1 (1100).

Bitwise NOT

The bitwise NOT operator (~) is conceptually straightforward: It simply flips each bit from a 0 to a 1, or vice versa.

~0011 is 1100
~0000 0100 is 1111 1011

#include <bitset>
#include <iostream>

int main()
{
    std::bitset<4> b4{ 0b100 }; // b4 is 0100
    std::bitset<8> b8{ 0b100 }; // b8 is 0000 0100

    std::cout << "Initial values:\n";
    std::cout << "Bits: " << b4 << ' ' << b8 << '\n';
    std::cout << "Values: " << b4.to_ulong() << ' ' << b8.to_ulong() << "\n\n";    

    b4 = ~b4; // flip b4 to 1011
    b8 = ~b8; // flip b8 to 1111 1011
    
    std::cout << "After bitwise NOT:\n";
    std::cout << "Bits: " << b4 << ' ' << b8 << '\n';
    std::cout << "Values: " << b4.to_ulong() << ' ' << b8.to_ulong() << '\n';    

    return 0;
}

Initial values:
Bits: 0100 00000100
Values: 4 4

After bitwise NOT:
Bits: 1011 11111011
Values: 11 251

Bitwise OR

Bitwise OR (|) works much like its logical OR counterpart. If you remember, logical OR evaluates to true (1) if either of the operands are true, otherwise it evaluates to false (0).

However, whereas logical OR is applied to the entire operand (to produce a single true or false result), bitwise OR is applied to each pair of bits in the operands (to produce a single true or false result for each bit).

Let’s illustrate this with an example. Consider the expression 0b0101 | 0b0110.

0 1 0 1 OR (or whatever bitwise operation you are doing)
0 1 1 0

In the first column, 0 OR 0 is 0, so we put a 0 underneath the line.

0 1 0 1 OR
0 1 1 0
-------
0

Second column, 1 OR 1 is 1. Third column 0 or 1 is 1. And fourth column, 1 or 0 is 1.

0 1 0 1 OR
0 1 1 0
-------
0 1 1 1

Our result is 0111 binary.

#include <bitset>
#include <iostream>

int main()
{
	std::cout << (std::bitset<4>{ 0b0101 } | std::bitset<4>{ 0b0110 }) << '\n';

	return 0;
}

This prints:

0111

We can do the same thing to compound bitwise OR expressions, such as 0b0111 | 0b0011 | 0b0001. If any of the bits in a column are 1, the result of that column is 1:

0 1 1 1 OR
0 0 1 1 OR
0 0 0 1
--------
0 1 1 1

Here’s code for the above:

#include <bitset>
#include <iostream>

int main()
{
	std::cout << (std::bitset<4>{ 0b0111 } | std::bitset<4>{ 0b0011 } | std::bitset<4>{ 0b0001 }) << '\n';

	return 0;
}

This prints:

0111

Bitwise AND

Bitwise AND (&) works similarly to the above, except it uses AND logic instead of OR logic. That is, for each pair of bits in the operands, Bitwise AND sets the resulting bit to true (1) if both paired bits are 1, and false (0) otherwise.

Consider the expression 0b0101 & 0b0110. Lining each of the bits up and applying bitwise AND to each column of bits:

0 1 0 1 AND
0 1 1 0
--------
0 1 0 0

#include <bitset>
#include <iostream>

int main()
{
	std::cout << (std::bitset<4>{ 0b0101 } & std::bitset<4>{ 0b0110 }) << '\n';

	return 0;
}

This prints:

0100

Similarly, we can do the same thing to compound bitwise AND expressions, such as 0b0001 & 0b0011 & 0b0111. If all of the bits in a column are 1, the result of that column is 1.

0 0 0 1 AND
0 0 1 1 AND
0 1 1 1
--------
0 0 0 1

#include <bitset>
#include <iostream>

int main()
{
	std::cout << (std::bitset<4>{ 0b0001 } & std::bitset<4>{ 0b0011 } & std::bitset<4>{ 0b0111 }) << '\n';

	return 0;
}

This prints:

0001

Bitwise XOR

The last operator is the bitwise XOR (^), also known as exclusive or.

For each pair of bits in the operands, Bitwise XOR sets the resulting bit to true (1) when exactly one of the paired bits is 1, and false (0) otherwise. Put another way, Bitwise XOR sets the resulting bit to true when the paired bits are different (one is a 0 and the other a 1).

Consider the expression 0b0110 ^ 0b0011:

0 1 1 0 XOR
0 0 1 1
-------
0 1 0 1

It is also possible to evaluate compound XOR expression column style, such as 0b0001 ^ 0b0011 ^ 0b0111. If there are an even number of 1 bits in a column, the result is 0. If there are an odd number of 1 bits in a column, the result is 1.

0 0 0 1 XOR
0 0 1 1 XOR
0 1 1 1
--------
0 1 0 1

Bitwise assignment operators

Similar to the arithmetic assignment operators, C++ provides bitwise assignment operators. These do modify the left operand.

For example, instead of writing x = x >> 1;, you can write x >>= 1;.

#include <bitset>
#include <iostream>

int main()
{
    std::bitset<4> bits { 0b0100 };
    bits >>= 1;
    std::cout << bits << '\n';

    return 0;
}

This program prints:

0010

Bitwise operators perform integral promotion on smaller integral types Advanced

If the operand(s) of a bitwise operator are an integral type smaller than an int, those operands will be promoted (converted) to int or unsigned int, and the result returned will also be an int or unsigned int. For example, if our operands are unsigned short, they will be promoted (converted) to unsigned int, and the result of the operation will be returned as an unsigned int.

In many cases, this won’t matter.

However, when using bitwise operators on integral types narrower than int or unsigned int, there are two cases to watch out for:

• operator~ and operator<< are width-sensitive and may produce different results depending on the width of the operand.
• Initializing or assigning the result to a variable of the smaller integral type is a narrowing conversion (since converting an int or unsigned int to a smaller integral type may result in data loss). This is disallowed in list initialization, and your compiler may or may not complain about a narrowing assignment.

The following program exhibits these issues (assuming 32-bit ints):

#include <bitset>
#include <cstdint>
#include <iostream>

int main()
{
    std::uint8_t c { 0b00001111 };
    
    std::cout << std::bitset<32>(~c) << '\n';     // incorrect: prints 11111111111111111111111111110000
    std::cout << std::bitset<32>(c << 6) << '\n'; // incorrect: prints 0000000000000000001111000000
    std::uint8_t cneg { ~c };                     // error: narrowing conversion from unsigned int to std::uint8_t
    c = ~c;                                       // possible warning: narrowing conversion from unsigned int to std::uint8_t
 
    return 0;
}

These issues can be addressed by using static_cast to convert the result of your bitwise operation back to the narrower integral type. The following program produces the correct results:

#include <bitset>
#include <cstdint>
#include <iostream>

int main()
{
    std::uint8_t c { 0b00001111 };

    std::cout << std::bitset<32>(static_cast<std::uint8_t>(~c)) << '\n';     // correct: prints 00000000000000000000000011110000
    std::cout << std::bitset<32>(static_cast<std::uint8_t>(c << 6)) << '\n'; // correct: prints 0000000000000000000011000000
    std::uint8_t cneg { static_cast<std::uint8_t>(~c) };                     // compiles
    c = static_cast<std::uint8_t>(~c);                                       // no warning
 
    return 0;
}

Summary

Summarizing how to evaluate bitwise operations utilizing the column method:

When evaluating bitwise OR, if any bit in a column is 1, the result for that column is 1.
When evaluating bitwise AND, if all bits in a column are 1, the result for that column is 1.
When evaluating bitwise XOR, if there are an odd number of 1 bits in a column, the result for that column is 1.

In the next lesson, we’ll explore how these operators can be used in conjunction with bit masks to facilitate bit manipulation.

Quiz time

Question #1

a) What does 0110 >> 2 evaluate to in binary?

Show Solution

b) What does the following evaluate to in binary: 0011 | 0101?

Show Solution

0 0 1 1 OR
0 1 0 1
--------
0 1 1 1

c) What does the following evaluate to in binary: 0011 & 0101?

Show Solution

0 0 1 1 AND
0 1 0 1
--------
0 0 0 1

d) What does the following evaluate to in binary (0011 | 0101) & 1001?

Show Solution

Inside the parenthesis:

0 0 1 1 OR
0 1 0 1
--------
0 1 1 1

Then:

0 1 1 1 AND
1 0 0 1
--------
0 0 0 1

Question #2

A bitwise rotation is like a bitwise shift, except that any bits shifted off one end are added back to the other end. For example 0b1001 << 1 would be 0b0010, but a left rotate by 1 would result in 0b0011 instead. Implement a function that does a left rotate on a std::bitset<4>. For this one, it’s okay to use test() and set().

The following code should execute:

#include <bitset>
#include <iostream>

// "rotl" stands for "rotate left"
std::bitset<4> rotl(std::bitset<4> bits)
{
// Your code here
}

int main()
{
	std::bitset<4> bits1{ 0b0001 };
	std::cout << rotl(bits1) << '\n';

	std::bitset<4> bits2{ 0b1001 };
	std::cout << rotl(bits2) << '\n';

	return 0;
}

and print the following:

0010
0011

Show Solution

#include <bitset>
#include <iostream>

std::bitset<4> rotl(std::bitset<4> bits)
{
	// keep track of whether the leftmost bit was a 1
	const bool leftbit{ bits.test(3) };

	bits <<= 1; // do left shift (which shifts the leftmost bit off the end)

	// if the left bit was a 1
	if (leftbit)
		bits.set(0); // set the rightmost bit to a 1

	return bits;
}

int main()
{
	std::bitset<4> bits1{ 0b0001 };
	std::cout << rotl(bits1) << '\n';

	std::bitset<4> bits2{ 0b1001 };
	std::cout << rotl(bits2) << '\n';

	return 0;
}

Question #3

Extra credit: Redo quiz #2 but don’t use the test and set functions (use bitwise operators).

Show Hint

Show Hint

Show Solution

#include <bitset>
#include <iostream>

// h/t to reader Chris for this solution
std::bitset<4> rotl(std::bitset<4> bits)
{
	// bits << 1 does the left shift
	// bits >> 3 handle the rotation of the leftmost bit
	return (bits<<1) | (bits>>3);
}

int main()
{
	std::bitset<4> bits1{ 0b0001 };
	std::cout << rotl(bits1) << '\n';

	std::bitset<4> bits2{ 0b1001 };
	std::cout << rotl(bits2) << '\n';

	return 0;
}