if we want least significant bit we use
a & ( ~a + 1)

but how to get most sinificant bit?

and there is another question:
- how to reverse the order of each bits (i mean flip bits) ?
Posted on 2002-01-22 05:07:32 by doby

if we want least significant bit we use
a & ( ~a + 1)

There's a more straight to the point way: use a & 1 instead. If you use a & ( ~a + 1) you will have to do a comparation to 1 as well, since your formula returns 1 when "mine" returns 1, but returns an "random" (so to speak) value when "mine" returns the proper 0. Really, if you want to know the state of a bit you've to just & that single bit with your variable.


but how to get most sinificant bit?

e.g. a & 2^31 (i.e. 0x80000000 or 2147483648)


and there is another question:
- how to reverse the order of each bits (i mean flip bits) ?

You have to use XOR.. e.g. a XOR 8 inverts the third bit (i.e. 8 = 2^3). You don't have to do only one bit at a time, you can do all the bits you want at a time. E.g. a = a XOR 25 inverts the 1st, the 3rd and the 4th bits of a.

If you want to reverse all bits, use NOT instead.

I'd suggest you to experiment a lot.. only this way you'll be able to master all of the above in a *intuitive* and intimate way, which is the best thing you can learn (better than any degree).

Greets,
Maverick
Posted on 2002-01-22 05:47:29 by Maverick
He wishes to find the least significant set bit in some number, and "a & (~a + 1)" does that, where as you are testing whether the first bit is set (subtly different)!

On the P6 core there are BSF and BSR mnemonics (they are also available on earlier designs, but are very slow), which will find the first (or last in the case of BSR) set bit in a register.

Bit flipping and reversing the order are different! Flipping a bit usually means notting it!

I presume you meant 1234 -> 4321 type of reversing...

It depends on the length of the bit string involved, if its 32 bits you can do something along the lines of this:


mov edx, src_bit_string
mov ecx, src_bit_length ; must be less than 32 in this case!

mov eax, 32
sub eax, ecx
shr edx, eax ; remove false bits at the end of the edx register

xor eax, eax
@@:
shr edx, 1
rcl eax, 1
dec ecx
jnz @B


If the bit string is longer than 32 you'll need some form of source & destination swapping. You may find that with a fixed length bit string you can get higher performance using a combination of shifts, ands, and ors (you can also use rol/ror and bswap to move byte chunks around for speed).

Mirno
Posted on 2002-01-22 06:24:33 by Mirno
Mirno, that exactly what i want.

from ur answer if i want the maximum speed, it's mean that my solution is
- on p6 -> use bsr,bsf
- on earlier cpu -> use a & (~a + 1)

right?

i have more question: what is the fastest way to count the total number of bit set?
ex. 01101 -> 3
10001 -> 2

thanks,
Doby
Posted on 2002-01-22 07:06:58 by doby
On P6 cores (PII, & PIII, I assume P4, and Athlons too), use BSF for first bit set, BSR for last bit set.
Otherwise use the a & (~a + 1), which in assembly you can replace the "not a / inc a" with "neg a"!

I'm not sure of how to find the last bit set in a number easily other than some scanning, or LUT method...

For an easy to program bit counter try somthing like this:


mov eax, src_to_bit_count
xor ecx, ecx ;will also clear the carry flag

@@:
adc ecx, 0
shl eax, 1
jnz @B

adc ecx, 0
; result in ecx


If you have some n byte string, and want to count them, it may be quicker to use a LUT.

------ Edit ------
I've just noticed I've gone slightly wrong in the last post...
The code for reversing bit order should be:


mov edx, src_bit_string
mov ecx, src_bit_length ; must be less than 32 in this case!
xor eax, eax

; Assume ecx is greater than zero to start with!

@@:
shr edx, 1
rcl eax, 1
dec ecx
jnz @B

; Result in eax, unused bits all set to zero


Mirno
Posted on 2002-01-22 07:45:17 by Mirno