0

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 ?

Peter Cordes
  • 328,167
  • 45
  • 605
  • 847
kiriloff
  • 25,609
  • 37
  • 148
  • 229
  • Did you try evaluating `(-x) & x` for some `x` values to see what happened? https://catonmat.net/low-level-bit-hacks explains how / why this and other bithacks work. (e.g. carry propagation through zeros vs. ones.) – Peter Cordes Aug 16 '21 at 11:39

1 Answers1

3

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

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:

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

phuclv
  • 37,963
  • 15
  • 156
  • 475
  • Unfortunately, my *GenuineIntel G3220* doesn't support BMI so I have to stay with good old instruction `BSF`, `BSR`. – vitsoft Aug 16 '21 at 07:31
  • 2
    @vitsoft: If you want to isolate the LSB without BMI instructions, you'd actually use `xor eax,eax` / `sub eax, edi` / `and eax, edi` to implement `(-x) & x`. Using `bsf` / `bts` (into an xor-zeroed reg) would be less efficient, especially if you care about portable performance on AMD CPUs. – Peter Cordes Aug 16 '21 at 11:37
  • https://catonmat.net/low-level-bit-hacks has nice explanations of *why/how* many of these lowest-set-bit bithack formulas work, with carry/borrow propagation through zeros vs ones. – Peter Cordes Aug 16 '21 at 11:41