BLSI instruction - Isolate lowest set bit

Question

Bit Manipulation Set contains BLSI - this instruction Extracts the lowest set bit from the source operand and set the corresponding bit in the destination register

Could you show an example illustrating what is referred to by the lowest set bit (last bit in binary representation of an operand ?), what is the performed operation, and in which context or for which kind of applications this operation is used ?

Answer 1

The lowest set bit is the least significant 1 bit. For example in 101011010110000 then the first 1 bit on the right beside 0000 is the lowest set bit, and _blsi_u32(0b101011010110000) returns 0b10000

The operation has also been described in the link above:

temp ← (-SRC) bitwiseAND (SRC);
SF ← temp[OperandSize -1];
ZF ← (temp = 0);
IF SRC = 0
    CF ← 0;
ELSE
    CF ← 1;
FI
DEST ← temp;

(-SRC) bitwiseAND (SRC) clears all but the least significant 1 bit. For more information about how that works read

• Why is "i & (i ^ (i - 1))" equivalent to "i & (-i)"
• how to understand i & -i in python? bit manipulation in python
• Why the bit operation i & (-i) equals to rightmost bit?
• meaning of (number) & (-number)

It's commonly used to iterate through the set bits, for example to count the number of set bits (not the most efficient method though), or to pack/deposit bits:

• Portable efficient alternative to PDEP without using BMI2?
• Standard C++11 code equivalent to the PEXT Haswell instruction (and likely to be optimized by compiler)

It's also used in the Fenwick tree. See sample C++ implementation