C++

C++ TutorialBasic input/output in c++C++ AlignmentC++ Argument Dependent Name LookupC++ Arithmitic MetaprogrammingC++ ArraysC++ Atomic TypesC++ AttributesC++ autoC++ Basic Type KeywordsC++ Bit fieldsC++ Bit ManipulationC++ Bit OperatorsC++ Build SystemsC++ C incompatibilitiesC++ C++11 Memory ModelC++ Callable ObjectsC++ Classes/StructuresC++ Client server examplesC++ Common compile/linker errors (GCC)C++ Compiling and BuildingC++ Concurrency with OpenMPC++ Const CorrectnessC++ const keywordC++ Constant class member functionsC++ constexprC++ ContainersC++ Copy ElisionC++ Copying vs AssignmentC++ Curiously Recurring Template Pattern (CRTP)C++ Date and time using chrono headerC++ Debugging and Debug-prevention Tools & TechniquesC++ decltypeC++ Digit separatorsC++ EnumerationC++ ExceptionsC++ Explicit type conversionsC++ Expression templatesC++ File I/OC++ Floating Point ArithmeticC++ Flow ControlC++ Fold ExpressionsC++ Friend keywordC++ function call by value vs. call by referenceC++ Function OverloadingC++ Function Template OverloadingC++ Futures and PromisesC++ Header FilesC++ Implementation-defined behaviorC++ Inline functionsC++ Inline variablesC++ IterationC++ IteratorsC++ KeywordsC++ LambdasC++ Layout of object typesC++ Linkage specificationsC++ LiteralsC++ LoopsC++ Memory managementC++ MetaprogrammingC++ Move SemanticsC++ mutable keywordC++ MutexesC++ NamespacesC++ Non-Static Member FunctionsC++ One Definition Rule (ODR)C++ Operator OverloadingC++ operator precedenceC++ OptimizationC++ Overload resolutionC++ Parameter packsC++ Perfect ForwardingC++ Pimpl IdiomC++ PointersC++ Pointers to membersC++ PolymorphismC++ PreprocessorC++ ProfilingC++ RAII: Resource Acquisition Is InitializationC++ Random number generationC++ Recursive MutexC++ Refactoring TechniquesC++ ReferencesC++ Regular expressionsC++ Resource ManagementC++ Return Type CovarianceC++ Returning several values from a functionC++ RTTI: Run-Time Type InformationC++ Scopes



C++ Bit Manipulation

From WikiOD

Remarks[edit | edit source]

In order to use std::bitset you will have to include <bitset> header.

#include <bitset>

std::bitset overloads all of the operator functions to allow the same usage as the c-style handling of bitsets.


References

Remove rightmost set bit[edit | edit source]

C-style bit-manipulation[edit | edit source]

template <typename T>
T rightmostSetBitRemoved(T n)
{
    // static_assert(std::is_integral<T>::value && !std::is_signed<T>::value, "type should be unsigned"); // For c++11 and later
    return n & (n - 1);
}

Explanation

  • if n is zero, we have 0 & 0xFF..FF which is zero
  • else n can be written 0bxxxxxx10..00 and n - 1 is 0bxxxxxx011..11, so n & (n - 1) is 0bxxxxxx000..00.

Toggling a bit[edit | edit source]

C-style bit-manipulation[edit | edit source]

A bit can be toggled using the XOR operator (^).

// Bit x will be the opposite value of what it is currently
number ^= 1LL << x;

Using std::bitset[edit | edit source]

std::bitset<4> num(std::string("0100"));
num.flip(2); // num is now 0000
num.flip(0); // num is now 0001
num.flip();  // num is now 1110 (flips all bits)

Checking a bit[edit | edit source]

C-style bit-manipulation[edit | edit source]

The value of the bit can be obtained by shifting the number to the right x times and then performing bitwise AND (&) on it:

(number >> x) & 1LL;  // 1 if the 'x'th bit of 'number' is set, 0 otherwise

The right-shift operation may be implemented as either an arithmetic (signed) shift or a logical (unsigned) shift. If number in the expression number >> x has a signed type and a negative value, the resulting value is implementation-defined.

If we need the value of that bit directly in-place, we could instead left shift the mask:

(number & (1LL << x));  // (1 << x) if the 'x'th bit of 'number' is set, 0 otherwise

Either can be used as a conditional, since all non-zero values are considered true.

Using std::bitset[edit | edit source]

std::bitset<4> num(std::string("0010"));
bool bit_val = num.test(1);  // bit_val value is set to true;

Set all bits[edit | edit source]

C-style bit-manipulation[edit | edit source]

x = -1; // -1 == 1111 1111 ... 1111b

(See here for an explanation of why this works and is actually the best approach.)

Using std::bitset[edit | edit source]

std::bitset<10> x;
x.set(); // Sets all bits to '1'

Clearing a bit[edit | edit source]

C-style bit-manipulation[edit | edit source]

A bit can be cleared using the bitwise AND operator (&).

// Bit x will be cleared
number &= ~(1LL << x);

Using std::bitset[edit | edit source]

reset(x) or set(x,false) - clears the bit at position x.

std::bitset<5> num(std::string("01100"));
num.reset(2);     // num is now 01000
num.reset(0);     // num is still 01000
num.set(3,false); // num is now 00000

Changing the nth bit to x[edit | edit source]

C-style bit-manipulation[edit | edit source]

// Bit n will be set if x is 1 and cleared if x is 0.
number ^= (-x ^ number) & (1LL << n);

Using std::bitset[edit | edit source]

set(n,val) - sets bit n to the value val.

std::bitset<5> num(std::string("00100"));
num.set(0,true);  // num is now 00101
num.set(2,false); // num is now 00001

Setting a bit[edit | edit source]

C-style bit manipulation[edit | edit source]

A bit can be set using the bitwise OR operator (|).

// Bit x will be set
number |= 1LL << x;

Using std::bitset[edit | edit source]

set(x) or set(x,true) - sets bit at position x to 1.

std::bitset<5> num(std::string("01100"));
num.set(0);      // num is now 01101
num.set(2);      // num is still 01101
num.set(4,true); // num is now 11110

Counting bits set[edit | edit source]

The population count of a bitstring is often needed in cryptography and other applications and the problem has been widely studied.

The naive way requires one iteration per bit:

unsigned value = 1234;
unsigned bits = 0;  // accumulates the total number of bits set in `n`

for (bits = 0; value; value >>= 1)
  bits += value & 1;

A nice trick (based on Remove rightmost set bit ) is:

unsigned bits = 0;  // accumulates the total number of bits set in `n`

for (; value; ++bits)
  value &= value - 1;

It goes through as many iterations as there are set bits, so it's good when value is expected to have few nonzero bits.

The method was first proposed by Peter Wegner (in CACM 3 / 322 - 1960) and it's well known since it appears in C Programming Language by Brian W. Kernighan and Dennis M. Ritchie.


This requires 12 arithmetic operations, one of which is a multication:

unsigned popcount(std::uint64_t x)
{
  const std::uint64_t m1  = 0x5555555555555555;  // binary: 0101...
  const std::uint64_t m2  = 0x3333333333333333;  // binary: 00110011..
  const std::uint64_t m4  = 0x0f0f0f0f0f0f0f0f;  // binary: 0000111100001111

  x -= (x >> 1) & m1;             // put count of each 2 bits into those 2 bits
  x = (x & m2) + ((x >> 2) & m2); // put count of each 4 bits into those 4 bits 
  x = (x + (x >> 4)) & m4;        // put count of each 8 bits into those 8 bits 
  return (x * h01) >> 56;  // left 8 bits of x + (x<<8) + (x<<16) + (x<<24) + ... 
}

This kind of implementation has the best worst-case behavior (see Hamming weight for further details).


Many CPUs have a specific instruction (like x86's popcnt) and the compiler could offer a specific (non standard) built in function. E.g. with g++ there is:

int __builtin_popcount (unsigned x);

Check if an integer is a power of 2[edit | edit source]

The n & (n - 1) trick (see Remove rightmost set bit) is also useful to determine if an integer is a power of 2:

bool power_of_2 = n && !(n & (n - 1));

Note that without the first part of the check (n &&), 0 is incorrectly considered a power of 2.

Bit Manipulation Application: Small to Capital Letter[edit | edit source]

One of several applications of bit manipulation is converting a letter from small to capital or vice versa by choosing a mask and a proper bit operation. For example, the a letter has this binary representation 01(1)00001 while its capital counterpart has 01(0)00001. They differ solely in the bit in parenthesis. In this case, converting the a letter from small to capital is basically setting the bit in parenthesis to one. To do so, we do the following:

/****************************************
convert small letter to captial letter.

     a: 01100001
  mask: 11011111  <-- (0xDF)  11(0)11111
      :---------
a&mask: 01000001  <-- A letter
*****************************************/

The code for converting a letter to A letter is

#include <cstdio>

int main()
{
    char op1 = 'a';  // "a" letter (i.e. small case)
    int mask = 0xDF; // choosing a proper mask

    printf("a (AND) mask = A\n");
    printf("%c   &   0xDF = %c\n", op1, op1 & mask);

    return 0;
}

The result is

$ g++ main.cpp -o test1
$ ./test1
a (AND) mask = A
a   &   0xDF = A

Credit:Stack_Overflow_Documentation