Find next power of two integer

[Skipper]

Hi all,

for an application I'm working on, I needed a somewhat quick method to find the next power of two value equal to or larger than any integer value I might have. I cooked something up that I might as well drop here, enjoy!

If there is a faster method to do this, I'd like to hear about it...

I tested this code on Win11/X64 using Purebasic 6.21

Code: Select all

; NextPowerOfTwo.pb - calculates next power of two integer bigger than x.i

Procedure.i NextPowerOfTwo(x.i)  
  If x <= 0 Or x > 2147483648  ; valid input range 1..2^31 for x64 integers
    Debug "NextPowerOfTwo() ERROR: Invalid input value -  " + Str(x)
    ProcedureReturn 0 
  Else 
    x - 1         ; ensures x.i itself is returned if already power of two,
    x | x >> 1    ; sets all bits to the right to 1 ...
    x | x >> 2
    x | x >> 4
    x | x >> 8
    x | x >> 16
    x + 1         ; ... then adds one to get the next power of two value.
    ProcedureReturn x
  EndIf  
EndProcedure

; Test driver
Procedure TestNextPowerOfTwo()
  Dim testValues.i(10)
  Define i.i
  Define result.i
  
  testValues(0) = 0
  testValues(1) = 2
  testValues(2) = 3
  testValues(3) = 15
  testValues(4) = 16
  testValues(5) = 31
  testValues(6) = 999999999999999
  testValues(7) = 65536
  testValues(8) = 6553500
  testValues(9) = 84
  
  For i = 0 To ArraySize(testValues()) - 1
    Result = NextPowerOfTwo(testValues(i))
    If Result > 0
      Debug "Input: " + Str(testValues(i)) + " => Next Power of Two: " + Str(result)
    EndIf
  Next
EndProcedure

TestNextPowerOfTwo()

[AZJIO]

I used this code

Code: Select all

EnableExplicit

#Window = 0
Enumeration
	#StrField
	#Editor
EndEnumeration

Procedure SizeWindowHandler()
	Protected w, h
	w = WindowWidth(#Window)
	h = WindowHeight(#Window)
	ResizeGadget(#StrField, #PB_Ignore, #PB_Ignore, w - 20 , #PB_Ignore)
	ResizeGadget(#Editor, #PB_Ignore, #PB_Ignore, w - 20 , h - 60)
EndProcedure

Procedure InputHandler()
	Protected i, x.q
	Protected flg_bin.q, y = -1
	flg_bin = Val(GetGadgetText(#StrField))
	For i = 63 To 0 Step -1
		If flg_bin >> i & 1
			y + 1
			If y
				Break
			EndIf
			x = 1 << i
		EndIf
	Next
	If y
		x * 2
	EndIf
	SetGadgetText(#Editor, Str(x))
EndProcedure


;-┌───GUI───┐
If OpenWindow(#Window, 0, 0, 320, 360, "max", #PB_Window_SystemMenu | #PB_Window_ScreenCentered | #PB_Window_SizeGadget | #PB_Window_MaximizeGadget | #PB_Window_MinimizeGadget)
	WindowBounds(#Window, 220, 160, #PB_Ignore, #PB_Ignore)
	StringGadget(#StrField, 10 , 10 , 300 , 30 , "", #PB_String_Numeric)
	EditorGadget(#Editor , 10 , 50 , 300 , 300, #PB_Editor_WordWrap)
	BindGadgetEvent(0, @InputHandler(), #PB_EventType_Change)
	BindEvent(#PB_Event_SizeWindow, @SizeWindowHandler())

;-┌───Loop───┐
	Repeat
		Select WaitWindowEvent()
			Case #PB_Event_CloseWindow
				CloseWindow(0)
				End
		EndSelect
	ForEver
EndIf

[Skipper]

Thanks Azjio,

your nicely structured code provides me with insights for other themes I was wrestling with (window client area(s) resizing...)

Btw: your method provides power-of-two integers smaller than the one I type in. My code returns the integer itself if it is already a power-of-two integer, otherwise it returns the next larger one.

Cheers
Skipper

[Little John]

Another way (not checked for speed):

Code: Select all

; tested with PB 6.21

Macro Pow2 (_x_)
   ; in : whole number >= 0
   ; out: 2^x
   
   (1 << (_x_))
EndMacro


Macro Ceil (_x_)
   ; -- round towards positive infinity
   ; in : any number
   ; out: smallest whole number greater than or equal to x
   
   IntQ(Round(_x_, #PB_Round_Up))
EndMacro


Procedure.d Log2 (x.d)
   ; in : x > 0
   ; out: logarithm of x to the base 2
   
   CompilerIf #PB_Compiler_Backend = #PB_Backend_Asm
      ! fld1
      ! fld qword [p.v_x]
      ! fyl2x
      ProcedureReturn
   CompilerElse
      ProcedureReturn Log(x) / Log(2.0)
   CompilerEndIf
EndProcedure


Define x.i

x = 17
Debug Pow2(Ceil(Log2(x)))
x = 32
Debug Pow2(Ceil(Log2(x)))

[Piero]

Thanks Azjio,

your nicely structured code provides me with insights for other themes I was wrestling with (window client area(s) resizing...)

Btw: your method provides power-of-two integers smaller than the one I type in. My code returns the integer itself if it is already a power-of-two integer, otherwise it returns the next larger one.

It works as supposed here on Mac… in case post your configuration

Edit: you probably used the link, NOT the code posted in this thread!

[Skipper]

Piero,

I documented my test configuration in my post now, thanks!

Skipper