Bit manipulation: Difference between revisions

Revision as of 11:04, 14 May 2023

Revision as of 15:14, 30 May 2023

Line 24:

== Example of bit manipulation ==

To determine if a number is a power of two, conceptually we may repeatedly do integer divide by two until the number won't divide by 2 evenly; if the only factor left is 1, the original number was a power of 2. Using bit and logical operators, there is a simple expression which will return true (1) or false (0):

number won't divide by 2 evenly; if the only factor left is 1, the original number was a power of 2. Using bit and logical operators, there is a simple expression which will return true (1) or false (0):

<syntaxhighlight lang="cpp">

bool isPowerOfTwo = (x != 0) && ((x & (x - 1)) == 0);

</syntaxhighlight>

The second methodhalf uses the fact that powers of two have one and only one bit set in their binary representation:

x == 0...0<span style="color:red">1</span>0...0

x-1 == 0...001...1

Line 41 ⟶ 40:

x & (x-1) == 0...<span style="color:red">1</span>...000...0

If inline [[assembly language]] code is used, then an instruction ([[popcnt]]) that counts the number of 1's or 0's in the operand might be available; an operand with exactly one '1' bit is a power of 2. However, such an instruction may have greater latency than the bitwise method above.

== Bit manipulation operations==