Is pow2

[Everything]

The classic way is something like

Code: Select all

Procedure  IsPow2(x.i)
  If x > 1 And x & (x - 1) = 0
    ProcedureReturn #True 
  EndIf   
EndProcedure 

How can I optimize it (with asm maybe)?


And one more question
There is Next_pow2 function

Code: Select all

Procedure Next_pow2(Value)
  !mov rcx, [p.v_Value]
  !dec rcx
  !bsr rcx, rcx
  !mov rax, 1
  !add rcx, 1
  !shl rax, cl
  ProcedureReturn
EndProcedure

And what about Prev_pow2 ?

[idle]

Inline with or without fix for case of zero

:edited re Demivec

Code: Select all

Macro _IsPowTwo(val) 
  Bool((val & (val - 1))=0)
EndMacro 

Macro _IsPowTwo1(val)
  Bool(val And Not(val & (val - 1)))
EndMacro   

Macro _NextPowTwo(Value)
  EnableASM 
  mov rcx, Value
  dec rcx
  bsr rcx, rcx
  mov rax, 1
  add rcx, 1
  shl rax, cl
  mov value, rax
  DisableASM 
EndMacro 

Macro _PrevPowTwo(Value)
  EnableASM 
  mov rcx, Value
  bsr rcx, rcx
  mov rax, 1
  shl rax, cl
  mov value, rax
  DisableASM 
EndMacro 

For a = 2 To 1024
  n = a
  _NextPowTwo(n)
  p = a
  _PrevPowTwo(p)
  Debug Str(n) + "\ " + a + " \" + Str(p) ; n >= a>= p
Next

[Demivec]

@idle: The macro for _NextPowTwo(Value) works great. However the macro for PrevPowTwo(Value) does not. It reports only the correct result for a value that is already a power of two otherwise it returns the power of two before the next lower power of two (see sample of test values below).

I used this test code with your routines:

Code: Select all

For a = 2 To 1024
  n = a
  _NextPowTwo(n)
  p = a
  _PrevPowTwo(p)
  Debug Str(n) + "\ " + a + " \" + Str(n) ; n >= a > p
Next
;results for a values of 2 through 16 ;goal is NextPowTwo >= a > PrevPowTwo but PrevPowTwo is only correct if a is a power of two.
;2\ 2 \1
;4\ 3 \1
;4\ 4 \2
;8\ 5 \2
;8\ 6 \2
;8\ 7 \2
;8\ 8 \4
;16\ 9 \4
;16\ 10 \4
;16\ 11 \4
;16\ 12 \4
;16\ 13 \4
;16\ 14 \4
;16\ 15 \4
;16\ 16 \8

[idle]

@idle: The macro for _NextPowTwo(Value) works great. However the macro for PrevPowTwo(Value) does not. It reports only the correct result for a value that is already a power of two otherwise it returns the power of two before the next lower power of two (see sample of test values below).

Good catch thanks, not enough coffee, think this is right

Code: Select all

Macro _NextPowTwo(Value)
  EnableASM 
  mov rcx, Value
  dec rcx
  bsr rcx, rcx
  mov rax, 1
  add rcx, 1
  shl rax, cl
  mov value, rax
  DisableASM 
EndMacro 

Macro _PrevPowTwo(Value)
  EnableASM 
  mov rcx, Value
  bsr rcx, rcx
  mov rax, 1
  shl rax, cl
  mov value, rax
  DisableASM 
EndMacro 

For a = 2 To 1024
  n = a
  _NextPowTwo(n)
  p = a
  _PrevPowTwo(p)
  Debug Str(n) + "\ " + a + " \" + Str(p) ; n >= a>= p
Next

[Everything]

Thanks! Very nice.

Code: Select all

Macro _IsPowTwo1(val)
  Bool(val And Not(val & (val - 1)))
EndMacro 

IMHO IsPowTwo1(1) should also return 0 (like in my procedure).
Also IMHO it would be convenient to have also bulletproof procedures (macros is limited in many cases + we can add zero case fix to _NextPowTwo and 0-1 fix to _PrevPowTwo)

My variant:

Code: Select all

Procedure Next_pow2(Val)
  !mov rcx, [p.v_Val]
  !cmp rcx, 2
  !jg @f
  !mov rax, 2
  ProcedureReturn 
  !@@:
  !dec rcx
  !bsr rcx, rcx
  !mov rax, 1
  !add rcx, 1
  !shl rax, cl
  ProcedureReturn

Procedure PrevPowTwo(Val)
  !mov rcx, [p.v_Val]
  !cmp rcx, 2
  !jg @f
  !mov rax, 2
  ProcedureReturn 
  !@@:
  !bsr rcx, rcx
  !mov rax, 1
  !shl rax, cl
  ProcedureReturn
EndProcedure
EndProcedure

[Everything]

Thanks! Very nice.

Code: Select all

Macro _IsPowTwo1(val)
  Bool(val And Not(val & (val - 1)))
EndMacro 

IMHO IsPowTwo1(1) should also return 0 (like in my procedure). What about asm version?
Also IMHO it would be convenient to have bulletproof procedures (macros is limited in many cases + we can add zero case fix to _NextPowTwo and 0-1 fix to _PrevPowTwo)

My variant:

Code: Select all

Procedure Next_pow2(Val)
  !mov rcx, [p.v_Val]
  !cmp rcx, 2
  !jg @f
  !mov rax, 2
  ProcedureReturn 
  !@@:
  !dec rcx
  !bsr rcx, rcx
  !mov rax, 1
  !add rcx, 1
  !shl rax, cl
  ProcedureReturn

Procedure Prev_Pow2(Val)
  !mov rcx, [p.v_Val]
  !cmp rcx, 2
  !jg @f
  !mov rax, 2
  ProcedureReturn 
  !@@:
  !bsr rcx, rcx
  !mov rax, 1
  !shl rax, cl
  ProcedureReturn
EndProcedure
EndProcedure

[idle]

In the general case 2^0 = 1 so its correct 1 is a power of 2
The macros IsPowTwo and IsPowTwo1 are fine to be used Inline due to the bool
and I don't think you'll get any speed up with assembly even if you use sse4 popcnt
it'll probably be slower

the advantage of the macros next and prev is simply that they're branch less and obviously no procedure overhead
depends if you need to call them 100,000s times.

Code: Select all

Procedure IsPowTwoSSE4(val) 
  EnableASM 
  !popcnt rax,[p.v_val]  
  !cmp rax,1 
  !JE lisp2
  !mov rax ,0
  !lisp2: 
  ProcedureReturn
  DisableASM 
EndProcedure    

[Everything]

In the general case 2^0 = 1 so its correct 1 is a power of 2

In general you are right, however in most cases we probably want '2' as result, let it be as an option )

I don't think you'll get any speed up

Procedures isn't about speed, just for convenience in case of rare calls.

And thx for SSE version!

[wilbert]

IMHO IsPowTwo1(1) should also return 0 (like in my procedure).

If you want to exclude 1 as a power of 2, you can do it like this.

Code: Select all

Procedure IsPow2(n)
  ; Power of 2 check
  ; with n=1 reporting false
  !xor rax, rax
  !mov rcx, [p.v_n]
  !mov rdx, rcx
  !sub rcx, 1
  !jbe .l0; jbe / jle / jb / jl
  !and rcx, rdx
  !jnz .l0
  !mov rax, 1
  !.l0:  
  ProcedureReturn
EndProcedure

In it's current form
Debug IsPow2($8000000000000000)
will report true as it treats it as an unsigned value.
If you also want that to report false because PB sees it as a negative value, you have to change jbe to jle
If you do not want to exclude 1 as a power of two, use jb or jl instead of jbe / jle.

[Everything]

Thank you, wilbert!