In Computer memory, where efficiency is paramount, an intriguing paradox arises when dealing with Boolean values. These values, representing the binary states of true (1) or false (0), inherently require only a single bit for storage. However, due to the smallest addressable unit being a byte on modern architectures (8 bits), Boolean variables are often allocated a full byte, leaving seven bits idle and unused.

In the ground scheme of programming, this byte-level granularity for Boolean values seldom poses a significant concern. In most scenarios, the luxury of abundant memory allows us to prioritize code clarity, understandability, and maintainability over the meticulous management of individual bits.

Yet, in the storage-intensive applications, where every bytes matters, a strategy emerges: the art of “packing” multiple Boolean values into a single bytes. This technique becomes a crucial optimization when striving for maximal memory efficiency. Bit-packing involves consolidating multiple Boolean values into a single bytes, optimizing storage efficiency. While this technique might not be universally applicable due to potential sacrifices in code readability, it becomes particularly useful in storage-intensive applications.

Understanding Bit Manipulation

Bit manipulation is a technique used in a variety of problems to get the solution in an optimized way. It is all about Bitwise Operators which directly works upon binary numbers. Below are the Bitwise Operators that are used:

• Bitwise AND (&) = Returns a 1 in each bit position for which the corresponding bits of both operands are 1.
• Bitwise OR (|) = Returns a 1 in each bit position for which the corresponding bits of either or both operands are 1.
• Bitwise XOR (^) = Returns a 1 in each bit position for which the corresponding bits of either but not both operands are 1. (or we can say that, when the corresponding bits of both the operands are different, not same).
• Bitwise NOT (!) = Inverts all the bits.

All data in computer programs are internally stored as bits, i.e., as numbers 0 and 1. Bit representation in programming, an n-bit integer is internally stored as a binary number that consists of n bits. For example, the C++ type int is a 32-bit type, which means that every int number consists of 32 bits. The int number 43 = 00000000000000000000000000101011. The bits in the representation are indexed from right to left. To convert a bit representation bk… b2 b1 b0into a number, we can use the formula bk 2^k + … + b2 2^2 + b1 2^1 + b0 2^0. E.g., 1*2^5 + 1*2^3 + 1*2^1 + 1*2^0 = 43.  

The bit representation of a number is either signed or unsigned. Usually, a signed representation used, which means that both negative and positive numbers can be represented. A signed variable of n bits can contains any integer between-2^(n-1) and 2^(n-1) - 1.

The first bit in a signed representation is the sign of the number, 0 for non-negative numbers, and 1 for negative numbers and the remaining (n-1) bits contain the magnitude of the number.

For signed integers, Two's complement is used which means that the opposite number of a number is calculated first inverting all the bits in the number, and then increasing the number by one.

For instance, the bit representation of -43 is:

11111111111111111111111111010101

For example:

#include <iostream>
using namespace std;

int main() {
    int a = 5; // 0101
    int b = 9; // 1001

    // Bitwise AND
    cout << "a & b = " << (a & b) << endl; // 0001

    // Bitwise OR
    cout << "a | b = " << (a | b) << endl; // 1101

    // Bitwise XOR
    cout << "a ^ b = " << (a ^ b) << endl; // 1100

    // Bitwise NOT
    cout << "~a = " << (~a) << endl; // 1111 1111 1111 1111 1111 1111 1111 1010
    cout << "~b = " << (~b) << endl; // 1111 1111 1111 1111 1111 1111 1111 0110

    return 0;
}

// Output
a & b = 1
a | b = 13
a ^ b = 12
~a = -6
~b = -10

Bit Flags

We have used variables to hold single values. However, instead of viewing objects as holding a single value, we can instead view them as a collection of individual bits. When individual bits of an object are used as Boolean values, the bits are called bit flags.

A bit flag is a binary digit (bit) within a larger binary number that acts as a switch - turned on (1) or off (off). These flags serves as indicators for specific conditions or settings. Instead of using separate Boolean values, you can pack multiple true/false states into a single variables, conserving memory and enhancing efficiency.

Consider a scenario where you have various configuration options for a system. Traditionally, you might use individually Boolean variables for each option. However, with bit flags, you can represent these options using a single integers, with each bit indicating the status of a specific setting.

Bit numbering

Bit numbering refers to the way individual bits within a binary number are labeled or indexed. The most common conventions for bit numbering are:

1. Least Significant Bit (LSB): This is the rightmost bit in a binary number. It holds the smallest value. For example, in the binary number 1101, the rightmost bit (1) is the LSB.
2. Most Significant Bit (MSB): Conversely, the MSB is the leftmost bit, holding the largest value. In the binary number 1101, the leftmost bit (1) is the MSB.

Bit Positions

When dealing with multi-bit values, each bit has a unique position or place value within the binary representation. The positions are typically denoted using powers of 2, starting from 0 for the rightmost bit. The general formula to calculate the value of a bit at a specific position is 2^n, where n is the bit position.

Lets illustrate this with an example:

Consider the binary number 1101. Here are the bit positions and their corresponding values:

• 2^0 rightmost bit = 1
• 2^1 = 2
• 2^2 = 4
• 2^3 leftmost bit = 8

The decimal equivalent of 1101 is calculated as 1.2^0 + 0.2^1 + 1.2^2 + 1.2^3 = 1 + 0 + 4 + 8 = 13.

Bit indexing

In programming, bit indexing is typically zero-based, meaning the rightmost bit is at index 0, the next bit at index 1, and so on. For example, in the binary number 1101, the bit at index 0 is 1, the bit at index 1 is 0, and so forth.

This convention aligns with the use of bitwise operators and shifting in many programming languages. For instance, the expression 1 << n in C++ represents shifting the bit 1 to the left by n positions, effectively setting the bit at index n to 1.

Leveraging Bitwise Operations

Bitwise operations play a pivotal role in manipulating and querying bit flags. Here are some common bitwise operations used with bit flags:

Checking Bit

Use the bitwise AND operator to check if a specific bit is set.

bool isSet = (number & (1 << bitPosition)) != 0;

Setting a Bit

Use the bitwise OR operator to set a specific bit.

number |= (1 << bitPosition);

Clearing a Bit

Use the bitwise AND operator with the complement of a shifted value to clear a specific bit.

number &= ~(1 << bitPosition);

Toggling a Bit

Use the bitwise XOR operator to toggle a specific bit.

number ^= (1 << bitPosition);

Manipulating bits via std::bitset

C++ provides the std::bitset class as part of the Standard Template Library (STL), offering a convenient and expressive way to perform bit manipulation without directly dealing with bitwise operators.

A bitset is an array of bools but each Boolean value is not stored in a separate byte instead, bitset optimizes the space such that each Boolean value takes 1-bit space only, so space taken by bitset is less than that of an array of bool or vector of bool.

• A limitation of the bitset is that the size must be known at compile time i.e. size of the bitset is fixed.

std::bitset is the class template for bitset that is defined inside <bitset> header file so we need to include the header file before using bitset in our program.

Syntax:

bitset<size> variable_name(initialization);

1. Uninitialized: All the bits will be set to zero.

bitset<size> variable_name;

2. Initialization with decimal integer: Bitset will represent the given decimal number in binary form.

bitset<size> variable_name(DECIMAL_NUMBER);

3. Initialization with binary string: Bitset will represent the given binary string.

bitset<size> variable_name(string("BINARY_STRING");
bitset<size> variable_name("BINARY_STRING");

Example:

#include <bitset>
#include <iostream>
 
using namespace std;
 
int main()
{
    // declaring an uninitialized bitset object
    bitset<8> uninitializedBitset;
 
    // initialization with decimal number
    bitset<8> decimalBitset(15);
 
    // initialization with binary string
    bitset<8> stringBitset(string("1111"));
 
    cout << "Uninitialized bitset: " << uninitializedBitset
         << endl;
    cout << "Initialized with decimal: " << decimalBitset
         << endl;
    cout << "Initialized with string: " << stringBitset
         << endl;
 
    return 0;
}

// Output
Uninitialized bitset: 00000000
Initialized with decimal: 00001111
Initialized with string: 00001111

std::bitset Member Functions

std::bitset class contains some useful member functions to work on the bitset objects. Here are them:

1. set(): It sets the bit to a given value at a particular index. If no parameter is passed, it sets all bits to 1. If only a single parameter is passed, it sets the bits at that particular index to 1.

Syntax:

set(int index, bool value)

Parameter: The function accepts two parameters which are described below:

• Index - This parameter specifies the position at which the bit has to be set. The parameter is an optional one.
• value - This parameter specified a boolean value which has to be set at the index. The parameter is an optional one.

If no parameter is passed, it sets all the bits to 1. If only a single parameter is passed, it sets the bit at that index.

Return value: The function does not return anything.

#include <bits/stdc++.h> 
using namespace std; 
  
int main() 
{ 
    // Initialization of bitset 
    bitset<4> b1(string("1100")); 
    bitset<6> b2(string("100100")); 
  
    // Function that resets all bits 
    cout << "Before applying set() function: "
         << b1 << endl; 
  
    b1.set(); 
    cout << "After applying set() function: "
         << b1 << endl; 
  
    // Function that resets all bits 
    cout << "Before applying set() function: "
         << b2 << endl; 
  
    b2.set(); 
    cout << "After applying set() function: "
         << b2 << endl; 
  
    return 0; 
} 

// Output
Before applying set() function: 1100
After applying set() function: 1111
Before applying set() function: 100100
After applying set() function: 111111

Example 2: 

#include <bits/stdc++.h> 
using namespace std; 
  
int main() 
{ 
    // Initialization of bitset 
    bitset<4> b1(string("1100")); 
    bitset<6> b2(string("100100")); 
  
    // Function that resets all bits 
    cout << "Before applying set() function: "
         << b1 << endl; 
  
    // single parameter is passed 
    b1.set(1); 
    cout << "After applying set(1) function: "
         << b1 << endl; 
  
    // Function that resets all bits 
    cout << "Before applying set() function: "
         << b2 << endl; 
  
    // both parameters is passed 
    b2.set(2, 0); 
    b2.set(4, 1); 
    cout << "After applying set(2, 0) and"
         << " set(4, 1) function: " << b2 << endl; 
  
    return 0; 
} 

// Output
Before applying set() function: 1100
After applying set(1) function: 1110
Before applying set() function: 100100
After applying set(2, 0) and set(4, 1) function: 110000

2. reset():

3. flip(): Flip the bit value at the given index.

4. count(): Count the number of set bits.

5. test(): Return the boolean value at given index.

6. any(): Check if any bit is set.

7. none(): Check if none bit is set.

8. all(): Check if all bit is set.

9. size(): Returns the size of the bitset.

10. to_string(): Convert bitset to std::string.

11. to_ulong(): Convert bitset to unsigned long.

12. to_ullong(): Convert bitset to unsigned long long.

#include <bitset>
#include <iostream>
 
using namespace std;
 
int main()
{
    // declaring index variable
    int index = 0;
 
    // declaring few bitset objects
    bitset<4> allSet("1111"), allUnset;
 
    cout << "any() value: " << boolalpha << allSet.any()
         << endl;
 
    cout << "all() value: " << allSet.all() << endl;
 
    cout << "none() value: " << allSet.none() << endl;
 
    cout << "test() at index 0: " << noboolalpha
         << allSet.test(index) << endl;
 
    cout << "size() value: " << allSet.size() << endl;
 
    cout << "Value of allUnset on before using set(): "
         << allUnset << endl;
    allUnset.set(index);
    cout << "Value of allUnset on after using set(): "
         << allUnset << endl;
 
    cout << "Value of allSet on before using reset(): "
         << allSet << endl;
    allSet.reset(index);
    cout << "Value of allSet on after using reset(): "
         << allSet << endl;
 
    // declaring an empty string
    string bitString;
    // using to_string() method to assign value to empty
    // string
    bitString = allSet.to_string();
    cout << "bitString: " << bitString << endl;
 
    cout << "Unsigned Long value: " << allSet.to_ulong();
 
    return 0;
}

// Output
any() value: true
all() value: true
none() value: false
test() at index 0: 1
size() value: 4
Value of allUnset on before using set(): 0000
Value of allUnset on after using set(): 0001
Value of allSet on before using reset(): 1111
Value of allSet on after using reset(): 1110
bitString: 1110
Unsigned Long value: 14

Note: boolalpha is used to print “true” and “false” instead of 1 or 0 for boolean values and noboolalpha for opposite.

std::bitset Operators

Some of the basic operators are overloaded to work with bitset objects. Following is the list of those operators:

1.  Access Operator: []

2. Bitwise And: &

3. Bitwise OR: |

4. Bitwise Not: ~

5. Binary Right shift and assign: >>=

6. Binary Left shift and assign: <<=

7. Assign the value of bitwise AND to the first bitset: &=

8. Assign the value of bitwise OR to the first bitset: |=

9. Assign the value of bitwise XOR to the first bitset: ^=

10. Bitwise NOT: ~

Example:

#include <bitset>
#include <iostream>

using namespace std;

int main()
{

	bitset<4> bitset1("1001"), bitset2("1010");
	bitset<4> result;

	cout << "Bitset1: " << bitset1
		<< "\nBitset2: " << bitset2 << endl;

	cout << "Accessing bit value at index 0 of bitset1: "
		<< bitset1[0] << endl;

	// bitwise AND
	cout << "Bitwise AND using &: "
		<< (result = bitset1 & bitset2) << endl;
	cout << "Bitwise AND using &=: " << (bitset1 &= bitset2)
		<< endl;

	// bitwise OR
	bitset1 = 9; // 9 = 1001
	cout << "Bitwise OR using |: "
		<< (result = bitset1 | bitset2) << endl;
	cout << "Bitwise OR using |=: " << (bitset1 |= bitset2)
		<< endl;

	// bitwise NOT
	cout << "Bitwise NOT: " << (result = ~bitset1) << endl;

	// bitwise XOR
	bitset1 = 9;
	cout << "Bitwise XOR: " << (bitset1 ^= bitset2) << endl;

	bitset1 = 9;
	cout << "Binary leftshift on bitwise1: "
		<< (bitset1 <<= 1) << endl;
	bitset1 = 9;
	cout << "Binary rightshift on bitwise1: "
		<< (bitset1 >>= 1) << endl;

	return 0;
}

// Output
Bitset1: 1001
Bitset2: 1010
Accessing bit value at index 0 of bitset1: 1
Bitwise AND using &: 1000
Bitwise AND using &=: 1000
Bitwise OR using |: 1011
Bitwise OR using |=: 1011
Bitwise NOT: 0100
Bitwise XOR: 0011
Binary leftshift on bitwise1: 0010
Binary rightshift on bitwise1: 0100