Efficient Bitwise Operations for Counting Bits or Find the Right|Left Most Ones

Efficient bitwise operations for counting bits or find the right|left most ones

If you want the fastest way, you will need to use non-portable methods.

Windows/MSVC:

• _BitScanForward()
• _BitScanReverse()
• __popcnt()

GCC:

• __builtin_ffs()
• __builtin_ctz()
• __builtin_clz()
• __builtin_popcount()

These typically map directly to native hardware instructions. So it doesn't get much faster than these.

But since there's no C/C++ functionality for them, they're only accessible via compiler intrinsics.

Efficient bitwise operation to find the index of the left|right most bit set

There is no access to compiler-specific "builtin" instructions for things like ffs. You would have to use a regular code implementation using things like bitmasks and shift operations. However, that doesn't necessarily mean you need to iterate over all the bits: there are some scary-clever "regular" implementations for many of these methods, doing crazy "add some bizarre constant that isn't obvious" that are designed to cut out most of the branching and iteration, and which would be perfectly fine in C#. The main thing to keep in mind if you port one of these is knowing whether it is using "signed" or "unsigned" right-shifts; if it is using "signed" use int (etc); if it is "unsigned", use uint (etc).

Bitwise operation to shift left AND change the right most bit?

Use bits = (bits << 1); to shift in a 0.
Use bits = (bits << 1) | 1; to shift in a 1.

How to find the index of the left-most 1 bit for x=2^k?

Many CPUs have a native hardware instruction, something like CTZ ("count trailing zeros"). GCC ex­po­ses this through the built-in function __builtin_ctz; other compilers should have similar facilities.

How to get position of right most set bit in C

Try this

int set_bit = n ^ (n&(n-1));

Explanation:

As noted in this answer, n&(n-1) unsets the last set bit.

So, if we unset the last set bit and xor it with the number; by the nature of the xor operation, the last set bit will become 1 and the rest of the bits will return 0

Zero all the bits after the 2nd index

If I understand you correct, and you want to preserve the lowest two bits and zero all the rest, you don't need a loop:

x &= 3

does exactly that with x.

Fastest way for getting last index of item in vector in C++?

Use std::max_element and reverse iterators. And that is looping through the vector. If it is unsorted, there is no faster way.

How to bitwise replace a range of bits in one number with the bits of another for incrementing, not affecting lower bits?

The simplest way to do this would be to increment starting after 4 bits, i.e.:

data_bits += 1 << 4;

This leaves the lower 4 bits unchanged.

---

Related Topics