Is there a fast way do determine if an integer is a power of 2?
If possible one without jumps.
If possible one without jumps.
Not tested but here goes:
Example 1:
4 = 100
4 - 1 = 3 = 011
ANDing 4 and 3
100
011
----
000 zero flag set!!!! 4 is a power of 2
Example 2:
15 = 1111
15 - 1 = 14 = 1110
ANDing 15 and 14
1111
1110
-----
1110 zero flag not set!!!! 15 isn't a power of 2
Example 3:
16 = 10000
16 - 1 = 15 = 01111
ANDing 16 and 15
10000
01111
------
00000 zero flag set!!! 16 is a power of 2
:) Sorry If I made a mistake on this one.
.data
nValue DD 16
.code
mov edx, nValue
mov eax, nValue
dec eax
and eax, edx
jnz @@NotPowerof2
Example 1:
4 = 100
4 - 1 = 3 = 011
ANDing 4 and 3
100
011
----
000 zero flag set!!!! 4 is a power of 2
Example 2:
15 = 1111
15 - 1 = 14 = 1110
ANDing 15 and 14
1111
1110
-----
1110 zero flag not set!!!! 15 isn't a power of 2
Example 3:
16 = 10000
16 - 1 = 15 = 01111
ANDing 16 and 15
10000
01111
------
00000 zero flag set!!! 16 is a power of 2
:) Sorry If I made a mistake on this one.
I would test the bits 1 by 1,
If there are two bits set, its no power of 2.
If there is 1 bit set, its a power of 2.
2^0=1 this is also a power of 2
dont ask me how to do it in code
:)
If there are two bits set, its no power of 2.
If there is 1 bit set, its a power of 2.
2^0=1 this is also a power of 2
dont ask me how to do it in code
:)
This isn't the best, but I just pulled it out of my hat...
; check if EAX is a power of 2
mov edx, eax
dec eax ; 2^x - 1
mov ecx, eax
not eax
shl eax,1
xor eax,ecx
xor eax, edx
; if EAX is -1, then power of two
inc eax
je PowerOfTwo
; check if EAX is a power of 2
mov edx, eax
dec eax ; 2^x - 1
mov ecx, eax
not eax
shl eax,1
xor eax,ecx
xor eax, edx
; if EAX is -1, then power of two
inc eax
je PowerOfTwo
Couldn't you just write:
mov eax,value
test eax,1 ;is it a power of one ?
je ;yes, then jump to Power of one.
xxx ;no, it's a power of two
xxx
;)
mov eax,value
test eax,1 ;is it a power of one ?
je ;yes, then jump to Power of one.
xxx ;no, it's a power of two
xxx
;)
Couldn't you just write:
{clip}
I guess your confused with a multiple of two?
Originally posted by stryker
4 = 1000
am I missing something here 4 = 1000 ?
is the binary number of 4 = 0100
and the binary number of 3 = 0011
4 = 1000
am I missing something here 4 = 1000 ?
is the binary number of 4 = 0100
and the binary number of 3 = 0011
Mine doesn't work? uhh I think it works perfectly.
Compile this proggy to test and try replacing the value with 5. This will popup yes (meaning 5 is a power of 2) :)
.586
.model flat, stdcall
OPTION SCOPED
OPTION CASEMAP:NONE
INCLUDE \masm32\include\kernel32.inc
INCLUDELIB \masm32\lib\kernel32.lib
INCLUDE \masm32\include\user32.inc
INCLUDELIB \masm32\lib\user32.lib
.DATA
notp2 DB "Not", 0
yesp2 DB "Yes", 0
value DD 6
.CODE
Start:
mov eax,value
test eax,1
je @PowerOfOne
;mov edx,value
;mov eax,value
;dec eax
;and eax, edx
;jnz @PowerOfOne
invoke MessageBox, 0, OFFSET yesp2, 0, 0
jmp @@Exit
@PowerOfOne:
invoke MessageBox, 0, OFFSET notp2, 0, 0
@@Exit:
invoke ExitProcess, 0
END Start
Compile this proggy to test and try replacing the value with 5. This will popup yes (meaning 5 is a power of 2) :)
stryker, nice try. Try ZERO?
0 AND -1 = 0, ERROR!
0 AND -1 = 0, ERROR!
Hello Stryker !
I didn't write anything about your code didn't work!
I only pointed out that:
am I missing something here 4 = 1000 ?
isn't the binary number of 4 = 0100
and the binary number of 3 = 0011
Regards,
The SharK
http://home19.inet.tele.dk/assembler
;)
I didn't write anything about your code didn't work!
I only pointed out that:
am I missing something here 4 = 1000 ?
isn't the binary number of 4 = 0100
and the binary number of 3 = 0011
Regards,
The SharK
http://home19.inet.tele.dk/assembler
;)
Sorry!!! Opps, he he !!! that code above is not "reliable". Maybe it'll be better go with FPU instruction fsqrt and check if it's a whole number.
This one will determine if a value is root of 2. Not the power of 2. :)
[size=9]
.586
.MODEL FLAT, STDCALL
OPTION SCOPED
OPTION CASEMAP:NONE
INCLUDE \masm32\include\kernel32.inc
INCLUDELIB \masm32\lib\kernel32.lib
INCLUDE \masm32\include\user32.inc
INCLUDELIB \masm32\lib\user32.lib
.DATA
notp2 DB "Not", 0
yesp2 DB "Yes", 0
value REAL8 16.0
.CODE
Start:
fld value
fsqrt
fstp value
fld value
frndint
fcomp value
fstsw ax
sahf
fstp value ;Rebalance FPU stack
jne @@NotPowerOf2
invoke MessageBox, 0, OFFSET yesp2, 0, 0
jmp @@Exit
@@NotPowerOf2:
invoke MessageBox, 0, OFFSET notp2, 0, 0
@@Exit:
invoke ExitProcess, 0
END Start
[/size]
PowerOfTwo MACRO regmem:REQ
;; return EAX zero if regmem is a power of two
mov eax, regmem
sub eax, 1
sbb edx,edx
and eax, regmem
xor eax, edx
ENDM
stryker, thanks for the idea. :)
Mirno, haste makes waste... :tongue:
; Value to test in eax
; We will splatter ecx, so make sure nothing in there!
bsf ecx, eax
jnz NoBitsSet
btr eax, ecx
bsf ecx, eax
jnz PowerOfTwo
If you count zero as a power of 2, then you can get rid of the "jnz NoBitsSet"...
Beware, this code will be quite slow on anything less than a PPro/P2!
----- Edit -----
Alternative (non-destructive)
bsf ecx, eax
;jnz NoBitsSet ;Optional
bsr edx, eax
cmp edx, ecx
jne NonPowerOfTwo
As for BitRAKEs method, why not:
PowerOfTwo MACRO regmem:REQ
;; return EAX zero if regmem is a power of two
mov eax, regmem
; mov edx, regmem ;Not needed
dec eax
sbb edx,edx
and eax, regmem
xor eax, edx
ENDM
Or even:
mov edx, eax
dec eax
and eax, edx
; eax zero of powers of 2, non-zero for not
Mirno
Its easy enough to test if its NOT a power of two, SHL SHR by whatever amount you want and see if the value is the same after.
Regards,
hutch@movsd.com
Regards,
hutch@movsd.com
Simple
Traditionally a non-zero value is TRUE, so you'd have to call this proc IsNotPowerOfTwo() for it to make sense. ;)
;on exit if number is a power of two,
;eax = zero, otherwise eax = non zero
;
;
mov eax, number ;load number to test
bsf ecx, eax ;find position of 1st on bit
;if no bits present, eax = 0
shr eax, cl ;shift the bit down
;if eax = 0 this does nothing.
dec eax ;if there was only 1 bit, eax = 1
; so dec eax would be zero
Traditionally a non-zero value is TRUE, so you'd have to call this proc IsNotPowerOfTwo() for it to make sense. ;)
If you just HAD to have it return a traditional bool:
Edit: Oops sorry. I see that somebody already posted a better version. Missed it first time around.
;bool IsPwr2( unsigned int )
;
;In - dword to test
;out - type bool. 1 = is. 0 = is not.
;
IsPwr2 proc number:DWORD
mov eax, number
bsf ecx, eax
shr eax, cl
cmp eax, 1
je @F
xor eax, eax
@@: ret
IsPwr2 endp
Edit: Oops sorry. I see that somebody already posted a better version. Missed it first time around.
hmm! I tested that algo but it returned something that it shouldn't.
- Number 0 it returned 0. 0 is a power of 2 ==> 0^2 = 0.
- Number 8 it returned 1. 8 is a power of 3 ==> 2^3 = 8.
- Number 9 it returned 0. 9 is a power of 2 ==> 3^2 = 9.
This is also where my first code fell(check the first reply). The numbers 0, 8 and 9 always screws up my first algo. The last stable solution I tested was the FPU code.
- Number 0 it returned 0. 0 is a power of 2 ==> 0^2 = 0.
- Number 8 it returned 1. 8 is a power of 3 ==> 2^3 = 8.
- Number 9 it returned 0. 9 is a power of 2 ==> 3^2 = 9.
This is also where my first code fell(check the first reply). The numbers 0, 8 and 9 always screws up my first algo. The last stable solution I tested was the FPU code.
Stryker - Powers of two:
2^0 = 1
2^1 = 2
2^2 = 4
2^3 = 8
2^4 = 16
etc...
"0^2 = 0" ( Zero is a power of zero )
"2^3 = 8" ( Eight is a power of 2 )
"3^2 = 9" ( Nine is a power of three )
2^0 = 1
2^1 = 2
2^2 = 4
2^3 = 8
2^4 = 16
etc...
- Number 0 it returned 0. 0 is a power of 2 ==> 0^2 = 0
"0^2 = 0" ( Zero is a power of zero )
- Number 8 it returned 1. 8 is a power of 3 ==> 2^3 = 8
"2^3 = 8" ( Eight is a power of 2 )
- Number 9 it returned 0. 9 is a power of 2 ==> 3^2 = 9.
"3^2 = 9" ( Nine is a power of three )
Oh sorry what was I thinking :) Geez!!! I need to clear my head :) Since I got caught with the functions i'm creating right now on determining n power. :)
I mistook it as power of x it should be root of x. :)
I mistook it as power of x it should be root of x. :)