Hello everyone
First, I'm sorry for English,is Bing translate
Sometimes I coincide with some easy things that do not find a solution
For the examination of a large number of possibilities I must search for the greatest number of reduction
What is the fastest way to make sure that byte contains the number 1 in only one of the eight Bits:
00000001b or:
00000010b or:
00000100b or:
00001000b or:
00010000b or:
00100000b or:
01000000b or:
10000000b
Check all the values are long way:
CMP eax,0000000001b
JNE @F
mov IsHave,1
JMP __Ex
@@: CMP eax,0000000010b
JNE @F
mov IsHave,1
JMP __Ex
@@: CMP eax,0000000100b
JNE @F
mov IsHave,1
JMP __Ex
@@: CMP eax,0000001000b
JNE @F
mov IsHave,1
JMP __Ex
@@: CMP eax,0000010000b
JNE @F
mov IsHave,1
JMP __Ex
@@: CMP eax,0000100000b
JNE @F
mov IsHave,1
JMP __Ex
@@: CMP eax,0001000000b
JNE @F
mov IsHave,1
JMP __Ex
@@: CMP eax,0010000000b
JNE __Ex
mov IsHave,1
__Ex:
Thank you
test al, 11111111b
popcnt(al)=1
i'm not sure that POPCNT is supported on some processors
well - i know there's a bit to test for it under CPUID, which implies some don't
i am using a pentium 4 prescott, and i don't think it supports POPCNT :(
POPCNT is the easy way, for sure, if it's supported
there used to be a sneaky trick for this - don't remember what it is
i guess you'd find the highest bit set and the lowest bit set and see if they're the same
to find the lowest bit set:
00101000 - original byte
00100111 - DEC a copy of the original
11011000 - NOT the decremented copy
00001000 - AND that back onto the original
EDIT: i guess you don't need to find the highest bit
just see if the "lowest bit" byte = original :shock:
mov al,ValueToTest
mov ah,al
dec ah
not ah
and ah,al
cmp al,ah
jz OnlyOneBitSet
ok - wrote a quicky test program
you have to test to see if it's 0, i guess...
0
1
2
4
8
16
32
64
128
mov al,ValueToTest
mov ah,al
dec ah
not ah
and ah,al
jz NotSingleBitSet
cmp al,ah
jz OnlyOneBitSet
NotSingleBitSet:
Quote from: jj2007 on March 11, 2015, 07:49:34 PM
test al, 11111111b
Sorry, I mistook this for "at least one", but you mean "only one". Here is code for "only one":
include \masm32\include\masm32rt.inc
.code
test1 db 01000000b ; 1 bit, OK
test2 db 01000010b ; 2 bits, bad
test3 db 00000000b ; 0 bits, bad
start:
mov esi, offset test1
Repeat 3
lodsb
call popCount
Endm
exit
popCount:
m2m ecx, 7
.Repeat
rol al, 1 ; sets carry if the bit is set
.if Carry?
inc ch
.endif
dec cl
.Until Sign?
movzx eax, ch
print str$(eax), 13, 10
ret
end startIf you need fast code but have no popcount CPU, see this thread (http://masm32.com/board/index.php?topic=3505.0), or use MasmBasic PopCount (http://www.webalice.it/jj2006/MasmBasicQuickReference.htm#Mb1029).
you could do a SCASB, too :P
.DATA
BitTable db 1,2,4,8,16,32,64,128
.CODE
mov al,ValueToTest
push edi
mov ecx,8
mov edi,offset BitTable
repnz scasb
pop edi
jz OnlyOneBitSet
.if Carry?
inc ch
.endif
Isn't there a jump or two here?
adc ch,0
hi sinsi, dave, jj2007
Quote from: dedndave on March 11, 2015, 08:23:00 PM
i'm not sure that POPCNT is supported on some processors
well - i know there's a bit to test for it under CPUID, which implies some don't
i am using a pentium 4 prescott, and i don't think it supports POPCNT :(
POPCNT is the easy way, for sure, if it's supported
You're right:
error A2085: instruction or register not accepted in current CPU modealso I confirm it by: CPUID TEST ECX,800000h
Quote from: dedndave on March 11, 2015, 09:19:31 PM
you could do a SCASB, too :P
.DATA
BitTable db 1,2,4,8,16,32,64,128
.CODE
mov al,ValueToTest
push edi
mov ecx,8
mov edi,offset BitTable
repnz scasb
pop edi
jz OnlyOneBitSet
My result in EAX, meaning I will reduce
mov al,ValueToTestAlso I don't use EDI, this means I will reduce
push edi
pop ediI will use:
mov ecx,8
mov edi,offset BitTable
repnz scasb
jz OnlyOneBitSet
:t
Oops, Thank you for all :biggrin:
that's probably a slow method - so slow that i didn't bother testing it :lol:
the best code seems to be what i posted in Reply #6
Intel(R) Pentium(R) 4 CPU 3.00GHz
DecNotAnd: 8 9 8 9 8
BsfShl: 11 11 11 11 11
Popcnt: POPCNT Not Supported By This CPU
i coded POPCNT EAX,EAX as
db 0F3h,0Fh,0B8h,0C0h
hope i got it right - lol
i couldn't find many good examples
Intel(R) Pentium(R) 4 CPU 2.26GHz
DecNotAnd: 7 8 8 7 7
BsfShl: 8 7 8 8 7
Popcnt: POPCNT Not Supported By This CPU
Press any key to continue ...
why not
mov al,ValueToTest
mov ah,al
neg ah
jz NotSingleBitSet
and ah,al
cmp al,ah
jz OnlyOneBitSet
NotSingleBitSet:
?
that might shave off a clock cycle or 2 on some machines :t
not much different on my old P4 prescott, though
Intel(R) Pentium(R) 4 CPU 3.00GHz
NegAnd: 8 8 7 8 8
DecNotAnd: 9 9 9 9 8
BsfShl: 11 11 11 11 11
Popcnt: POPCNT Not Supported By This CPU
EDIT: oops! updated the attachment and my timings
rrr314159
Intel(R) Pentium(R) 4 CPU 2.26GHz
NegAnd: 5 5 6 6 6
DecNotAnd: 6 6 6 6 6
BsfShl: 7 8 7 7 7
Popcnt: POPCNT Not Supported By This CPU
Press any key to continue ...
Dave, you forgot to return procedure "IsP2Byte_DecNotAnd " after you modify it
IsP2Byte_DecNotAnd PROC dwVal:DWORD
movzx edx,byte ptr [esp+4]
xor eax,eax
mov dh,dl
; dec dh
; not dh
neg dh
; and dh,dl
.if !ZERO?
and dh,dl
.if dl==dh
mov al,1
.endif
.endif
ret 4
IsP2Byte_DecNotAnd ENDP
Intel(R) Pentium(R) 4 CPU 2.26GHz
NegAnd: 5 6 6 5 5
DecNotAnd: 7 8 8 8 7
BsfShl: 8 7 7 7 7
Popcnt: POPCNT Not Supported By This CPU
Press any key to continue ...
:t
Actually I wasn't thinking so much of the time (who cares about a clock cycle or two?) but it's a little cleaner. After all dec-not is precisely identical to neg, which is usually defined "take two's complement and add one". And, make the branch as soon as possible. But, just nit-picking; obviously my social life must be slow at the moment ... ;)
oops! good catch :t
updated attachment and timings in Reply #14
Intel(R) Core(TM) i7-4790 CPU @ 3.60GHz
NegAnd: 1 1 1 1 1
DecNotAnd: 2 2 2 2 2
BsfShl: 2 2 2 2 2
Popcnt: 0 0 0 0 0
:biggrin:
:biggrin: