Remove MSB

[lucasart]

Remove LSB: b &= b-1

Is there an equivalent trick to remove the MSB ?

[cdani]

I only know thinks more complicated like thins one:

unsigned resetLeadingBit(x) {
return x & ~(0x80000000U >> _BitScanReverse(x))
}

[lucasart]

I only know thinks more complicated like thins one:

unsigned resetLeadingBit(x) {
return x & ~(0x80000000U >> _BitScanReverse(x))
}

That's not a trick. You're calling _BitScanReverse() = msb().

And I think your code is wrong. It shoud be 1ULL << msb(x), not 0x80000000ULL >> msb(x).

Perhaps there is no trick, and x &= ~(1ULL << msb(x)) is the way to go.

[mar]

That's not a trick. You're calling _BitScanReverse() = msb().

And I think your code is wrong. It shoud be 1ULL << msb(x), not 0x80000000ULL >> msb(x).

Perhaps there is no trick, and x &= ~(1ULL << msb(x)) is the way to go.

No, his code is right (if x is 32-bit), I would probably prefer doing x & ((~0ull>>1)>>bsr),
_BitScanReverse is equivalent to builtin_clz (and so is the x86 bsr instruction)

The question is interesting though.
Since ARM has no CTZ instruction, well... Unfortunately most common versions are only 32 bit...
I tried using builtin_ctz recently and found it superior to builtin_ffs (at least with gcc) on ARM (I used a specialized two part 32-bit version),
the compiler somehow managed to transform it into CLZ but I couldn't find rbit (bit reversal instruction).
I haven't examined the assembly further, but it looked pretty good to me (nicer than ffs).

[hgm]

No such trick; carry propagates from lower to higher significance.

Without specialized instructions to do this, the fastest way would be to invert the bit order (which is an N log(N) process) and extract the LSB. Or perhaps a binary search on the bit, which also takes N log(N).

[Rein Halbersma]

No such trick; carry propagates from lower to higher significance.

Without specialized instructions to do this, the fastest way would be to invert the bit order (which is an N log(N) process) and extract the LSB. Or perhaps a binary search on the bit, which also takes N log(N).

Finding msb is Log(N), not N log(N)

[hgm]

Oops, you are right. I ignored that N bits are done in parallel. And without that it would of course just be O(N), as you would simply scan.

[Rein Halbersma]

Oops, you are right. I ignored that N bits are done in parallel. And without that it would of course just be O(N), as you would simply scan.

In fact, the log base 2 is equal to the msb

[Sven]

Oops, you are right. I ignored that N bits are done in parallel. And without that it would of course just be O(N), as you would simply scan.

In fact, the log base 2 is equal to the msb

See also various implementations of "bitScanReverse" in https://chessprogramming.wikispaces.com/BitScan

[Henk]

Oops, you are right. I ignored that N bits are done in parallel. And without that it would of course just be O(N), as you would simply scan.

In fact, the log base 2 is equal to the msb

Yes I used:

Code: Select all

    public class BitBoardBackwardIterator: IBitBoardIterator
    {
        UInt64 bits;


        public void Reset(UInt64 bits)
        {
            this.bits = bits;
        }

        public UInt64 Next()
        {
            while (bits != 0)
            {
                int index = (int)Math.Log(bits, 2);
                UInt64 bit = ((UInt64)1 << index);

                bits &= ~bit;
                return bit;
            }
            return 0;
       }
    }