PureBasic Forums - English

http://www.purebasic.com
https://www.purebasic.fr/english/

Bit Shifting

https://www.purebasic.fr/english/viewtopic.php?t=80707

Page 2 of 3

Re: Bit Shifting

Posted: Tue Feb 07, 2023 9:04 pm
by interfind
I have made a quick and dirty example to show what i want in Assembly.
Here i only have 6 Bit's permutation, but with more the sequence is the same.
Start with all Bit's on the right side.

Is this possible without loops?

Code: Select all

Procedure BitSet(VAR, NR)
  EnableASM
  MOV rbx, [p.v_NR]
  DEC rbx
  MOV rax, [p.v_VAR]
  BTS rax, rbx
  DisableASM
ProcedureReturn	
EndProcedure

Procedure BitClear(VAR, NR)
  EnableASM
  MOV rbx, [p.v_NR]
  DEC rbx
  MOV rax, [p.v_VAR]
  BTC rax, rbx
  DisableASM
ProcedureReturn	
EndProcedure

Start=0: X=1

  For a=1 To 44
    Start=BitSet(Start, a)  
      For b=1+a To 45
      Start=BitSet(Start, b)  
        For c=1+b To 46
          Start=BitSet(Start, c)
          For d=1+c To 47
            Start=BitSet(Start, d)  
            For e=1+d To 48
             Start=BitSet(Start, e)  
              For f=1+e To 49
                Start=BitSet(Start, f)  
                Debug RSet(Bin(Start+ROL), 49, "0") + " - " + Str(X)
                Start=BitClear(Start, f)         
                X+1
              Next
                Start=BitClear(Start, e)   
            Next
        Start=BitClear(Start, d) 
          Next
      Start=BitClear(Start, c) 
        Next
    Start=BitClear(Start, b) 
      Next
  Start=BitClear(Start, a) 
  Next

Re: Bit Shifting

Posted: Tue Feb 07, 2023 9:22 pm
by mk-soft
A old project from me, no c-backend ...

Link: Bitshift and Rotation

Re: Bit Shifting

Posted: Tue Feb 07, 2023 9:29 pm
by NicTheQuick
interfind wrote: Tue Feb 07, 2023 9:04 pm Is this possible without loops?
In my opinion you either need recursion or some sort of self built stack and a loop. Because as you already found out you need more and more nested loops to make this work with higher bit counts. Now try to use static arrays which hold the values of the start, end and loop variables to integrate all the for loops into one big loop.

Re: Bit Shifting

Posted: Tue Feb 07, 2023 9:36 pm
by interfind
NicTheQuick wrote: Tue Feb 07, 2023 9:29 pm
interfind wrote: Tue Feb 07, 2023 9:04 pm Is this possible without loops?
In my opinion you either need recursion or some sort of self built stack and a loop. Because as you already found out you need more and more nested loops to make this work with higher bit counts. Now try to use static arrays which hold the values of the start, end and loop variables to integrate all the for loops into one big loop.
i'm looking for somthing like that:

https://graphics.stanford.edu/~seander/bithacks.html
See on the end of side!

t = v | (v - 1)
v = (t + 1) | (((~t & -~t) - 1) >> (BSF + 1))

But with the sequence from my Example.

Re: Bit Shifting

Posted: Tue Feb 07, 2023 10:01 pm
by idle
what is the goal of this, what are you wanting to do?

Re: Bit Shifting

Posted: Wed Feb 08, 2023 7:20 am
by juergenkulow

Code: Select all

; 6 out 49 
Procedure BitSet(VAR, NR)
  EnableASM
  MOV rbx, [p.v_NR]
  DEC rbx
  MOV rax, [p.v_VAR]
  BTS rax, rbx
  DisableASM
ProcedureReturn	
EndProcedure

Procedure BitClear(VAR, NR)
  EnableASM
  MOV rbx, [p.v_NR]
  DEC rbx
  MOV rax, [p.v_VAR]
  BTC rax, rbx
  DisableASM
ProcedureReturn	
EndProcedure

Dim lottoset.q(13983817)
Start=0: X=1
DisableDebugger
For a=1 To 44
  Start=BitSet(Start, a)  
  For b=1+a To 45
    Start=BitSet(Start, b)  
    For c=1+b To 46
      Start=BitSet(Start, c)
      For d=1+c To 47
        Start=BitSet(Start, d)  
        For e=1+d To 48
          Start=BitSet(Start, e)  
          For f=1+e To 49
            Start=BitSet(Start, f)  
            lottoset(X)=Start
            Start=BitClear(Start, f)         
            X+1
          Next
          Start=BitClear(Start, e)   
        Next
        Start=BitClear(Start, d) 
      Next
      Start=BitClear(Start, c) 
    Next
    Start=BitClear(Start, b) 
  Next
  Start=BitClear(Start, a) 
  
Next
EnableDebugger

For i=1 To 10
  Debug RSet(Bin(lottoset(i)), 49, "0") + " - " + Str(i)
Next

Debug "4444444444333333333322222222221111111111"
Debug "9876543210987654321098765432109876543210987654321"
Debug RSet(Bin(lottoset(Random(13983816,1))), 49, "0")
; 0000000000000000000000000000000000000000000111111 - 1
; 0000000000000000000000000000000000000000001011111 - 2
; 0000000000000000000000000000000000000000010011111 - 3
; 0000000000000000000000000000000000000000100011111 - 4
; 0000000000000000000000000000000000000001000011111 - 5
; 0000000000000000000000000000000000000010000011111 - 6
; 0000000000000000000000000000000000000100000011111 - 7
; 0000000000000000000000000000000000001000000011111 - 8
; 0000000000000000000000000000000000010000000011111 - 9
; 0000000000000000000000000000000000100000000011111 - 10
; 4444444444333333333322222222221111111111
; 9876543210987654321098765432109876543210987654321
; 0000000000000000010000001000100001000000010100000

Re: Bit Shifting

Posted: Wed Feb 08, 2023 9:08 am
by interfind
juergenkulow wrote: Wed Feb 08, 2023 7:20 am

Code: Select all

; 6 out 49 
Procedure BitSet(VAR, NR)
  EnableASM
  MOV rbx, [p.v_NR]
  DEC rbx
  MOV rax, [p.v_VAR]
  BTS rax, rbx
  DisableASM
ProcedureReturn	
EndProcedure

Procedure BitClear(VAR, NR)
  EnableASM
  MOV rbx, [p.v_NR]
  DEC rbx
  MOV rax, [p.v_VAR]
  BTC rax, rbx
  DisableASM
ProcedureReturn	
EndProcedure

Dim lottoset.q(13983817)
Start=0: X=1
DisableDebugger
For a=1 To 44
  Start=BitSet(Start, a)  
  For b=1+a To 45
    Start=BitSet(Start, b)  
    For c=1+b To 46
      Start=BitSet(Start, c)
      For d=1+c To 47
        Start=BitSet(Start, d)  
        For e=1+d To 48
          Start=BitSet(Start, e)  
          For f=1+e To 49
            Start=BitSet(Start, f)  
            lottoset(X)=Start
            Start=BitClear(Start, f)         
            X+1
          Next
          Start=BitClear(Start, e)   
        Next
        Start=BitClear(Start, d) 
      Next
      Start=BitClear(Start, c) 
    Next
    Start=BitClear(Start, b) 
  Next
  Start=BitClear(Start, a) 
  
Next
EnableDebugger

For i=1 To 10
  Debug RSet(Bin(lottoset(i)), 49, "0") + " - " + Str(i)
Next

Debug "4444444444333333333322222222221111111111"
Debug "9876543210987654321098765432109876543210987654321"
Debug RSet(Bin(lottoset(Random(13983816,1))), 49, "0")
; 0000000000000000000000000000000000000000000111111 - 1
; 0000000000000000000000000000000000000000001011111 - 2
; 0000000000000000000000000000000000000000010011111 - 3
; 0000000000000000000000000000000000000000100011111 - 4
; 0000000000000000000000000000000000000001000011111 - 5
; 0000000000000000000000000000000000000010000011111 - 6
; 0000000000000000000000000000000000000100000011111 - 7
; 0000000000000000000000000000000000001000000011111 - 8
; 0000000000000000000000000000000000010000000011111 - 9
; 0000000000000000000000000000000000100000000011111 - 10
; 4444444444333333333322222222221111111111
; 9876543210987654321098765432109876543210987654321
; 0000000000000000010000001000100001000000010100000
Du hast alle Kobinantionen in das Array lottoset.q gepackt.

Bei 6 gesetzen Bit's kann man das noch machen.
Vorteil ist hier das ich sofort anhand des Array Index
die dazugehörige Kombinantion ermitteln kann.

Leider wird das aber bei 9 oder mehr gesetzen Bits
wegen Speicher und Zeit nicht mehr funktionieren.

Ausserdem will ich ja die Funktion ansich
möglichst effizent optimieren.

Re: Bit Shifting

Posted: Wed Feb 08, 2023 9:11 am
by interfind
idle wrote: Tue Feb 07, 2023 10:01 pm what is the goal of this, what are you wanting to do?
I want do calculate all posibble combinations for the given
set of Bit's.

This is for a Lottery Programm i want do programming. :)

Re: Bit Shifting

Posted: Wed Feb 08, 2023 11:25 am
by interfind
Here is what i want but with the permutations sequence from my last Post's.

Code: Select all

Define QPC_TICKS_PER_SECOND.l
Define QPC_Time_freq.q
Define QPC_Time_start.q

Procedure.l initTime(ticks_per_second.l=1000)
  Shared QPC_TICKS_PER_SECOND.l
  Shared QPC_Time_freq.q
  Shared QPC_Time_start.q
  If Not QueryPerformanceFrequency_(@QPC_Time_freq.q)
    ProcedureReturn 0
  Else
    QueryPerformanceCounter_(@QPC_Time_start.q)
    QPC_TICKS_PER_SECOND.l = ticks_per_second
    ProcedureReturn 1
  EndIf
EndProcedure
initTime(10000)
 
Procedure.l getTime()
  Shared QPC_TICKS_PER_SECOND.l
  Shared QPC_Time_freq.q
  Shared QPC_Time_start.q
  Protected QPC_Time_now.q
  QueryPerformanceCounter_(@QPC_Time_now.q)
  ProcedureReturn (QPC_Time_now - QPC_Time_start) * QPC_TICKS_PER_SECOND / QPC_Time_freq
EndProcedure


Procedure NBP_PB(v) ;Next Bit Permutation
  
  highestBit.i
  !BSF rcx, [p.v_v]           ;BitScanForward
  !MOV [p.v_highestBit], rcx  ;rcx = highestBit in v
  
  t = v | (v - 1)
  v = (t + 1) | (((~t & -~t) - 1) >> (highestBit + 1))
  
  ProcedureReturn v
  
EndProcedure

length.i=13983815   ;All combinations with 6 from 49

v.i=%00000000000000000000000000111111 ;start combination
w.i=v
StartTime = getTime()

For a=1 To length
  v=NBP_PB(v)
  Debug RSet(Bin(v), 50, "0")
Next a

CountTime$=StrD((getTime()-StartTime)/10000) + " Sekunden"

MessageRequester("Result", "Combinations: " +
                           FormatNumber(length, 0, "",".") + #LF$ +
                           CountTime$ + #LF$ +
                           "START: " + RSet(Bin(w), 49, "0") + #LF$ +
                           "END: " + RSet(Bin(v), 49, "0"))

Re: Bit Shifting

Posted: Wed Feb 08, 2023 12:34 pm
by SPH
very confused this post

Re: Bit Shifting

Posted: Wed Feb 08, 2023 1:07 pm
by Caronte3D
interfind wrote: Wed Feb 08, 2023 9:11 am I want do calculate all posibble combinations for the given
set of Bit's.
If you don't need an exact sequence of bits, why not simply increment 1 each time?

Re: Bit Shifting

Posted: Wed Feb 08, 2023 7:33 pm
by idle
Is the purpose to pick lotto sequences
If so just call random until you've sieved out 6 balls or however many you need to pick.

Re: Bit Shifting

Posted: Wed Feb 08, 2023 11:03 pm
by juergenkulow
Wiki Combination
[

Code: Select all

; NBP_PB C Backend optimized 
DisableDebugger
Procedure NBP_PB(v) ;Next Bit Permutation
  highestbit.i
  CompilerIf #PB_Compiler_Backend=#PB_Backend_Asm
    !BSF rcx, [p.v_v]           ;BitScanForward
    !MOV [p.v_highestbit], rcx  ;rcx = highestBit in v
  CompilerElse ; #PB_Compiler_Backend=#PB_Backend_C
    ! asm volatile(	"bsfq %1,%%rcx;"
    ! "movq %%rcx,%0;"
    ! : "=r"(v_highestbit) : "rm"(v_v)); 
  CompilerEndIf   
  t = v | (v - 1)
  v = (t + 1) | (((~t & -~t) - 1) >> (highestbit + 1))
  ProcedureReturn v
EndProcedure

Procedure.q binominal_coeffcient(n,k) ; n!/(k!*(n-k)!)
  Protected i,l=1,m=1
  For i=n-k+1 To n
    m*i
  Next
  For i=1 To k
    l*i
  Next 
  ProcedureReturn m/l
EndProcedure

k=Val(InputRequester("k:","k:","6"))
n=Val(InputRequester("n:","n:","49")) 
combinations.q=binominal_coeffcient(n,k) 
jmax.q=combinations/10
If jmax>10000000
  jmax=10000000
EndIf 
For i=1 To k 
  v=v<<1+1
Next 
StartTime = ElapsedMilliseconds()
For i=1 To combinations-1
  If j<=2
    EnableDebugger
    Debug RSet(Bin(v), n, "0")+" i:"+Str(i)+" "+Str(ElapsedMilliseconds()-StartTime)+" milliseconds"
    If j=2
      Debug "..." ; and so on 
    EndIf 
    DisableDebugger
    j+1
  ElseIf j>=jmax
    j=0
  Else
    j+1
  EndIf   
  v=NBP_PB(v)
Next 
EnableDebugger
Debug RSet(Bin(v), n, "0")+" i:"+Str(i)+" "+Str(ElapsedMilliseconds()-StartTime)+" milliseconds"

; 0000000000000000000000000000000000000000000111111 i:1 0 milliseconds
; 0000000000000000000000000000000000000000001011111 i:2 0 milliseconds
; 0000000000000000000000000000000000000000001101111 i:3 0 milliseconds
; ...
; 0000000000000010000000010000000000000100000110100 i:1398383 13 milliseconds
; 0000000000000010000000010000000000000100000111000 i:1398384 13 milliseconds
; 0000000000000010000000010000000000000100001000011 i:1398385 13 milliseconds
; ...
; 0000000000100000000000000100000100000000011010000 i:2796765 25 milliseconds
; 0000000000100000000000000100000100000000011100000 i:2796766 25 milliseconds
; 0000000000100000000000000100000100000000100000011 i:2796767 25 milliseconds
; ...
; 0000000010000100010000000000000011000000000010000 i:4195147 37 milliseconds
; 0000000010000100010000000000000011000000000100000 i:4195148 37 milliseconds
; 0000000010000100010000000000000011000000001000000 i:4195149 37 milliseconds
; ...
; 0000001000000100000010100000000000000000110000000 i:5593529 48 milliseconds
; 0000001000000100000010100000000000000001000000001 i:5593530 48 milliseconds
; 0000001000000100000010100000000000000001000000010 i:5593531 48 milliseconds
; ...
; 0000011000000001000100000001000000000000000010000 i:6991911 56 milliseconds
; 0000011000000001000100000001000000000000000100000 i:6991912 56 milliseconds
; 0000011000000001000100000001000000000000001000000 i:6991913 56 milliseconds
; ...
; 0001000000000001000000000010000010000000010000001 i:8390293 63 milliseconds
; 0001000000000001000000000010000010000000010000010 i:8390294 63 milliseconds
; 0001000000000001000000000010000010000000010000100 i:8390295 63 milliseconds
; ...
; 0010000000001001000100001000000000010000000000000 i:9788675 71 milliseconds
; 0010000000001001000100001000000000100000000000000 i:9788676 71 milliseconds
; 0010000000001001000100001000000001000000000000000 i:9788677 71 milliseconds
; ...
; 0100000000010000000000010000001010000000000000001 i:11187057 79 milliseconds
; 0100000000010000000000010000001010000000000000010 i:11187058 79 milliseconds
; 0100000000010000000000010000001010000000000000100 i:11187059 79 milliseconds
; ...
; 1000000000000010011000000000000100000001000000000 i:12585439 87 milliseconds
; 1000000000000010011000000000000100000010000000000 i:12585440 87 milliseconds
; 1000000000000010011000000000000100000100000000000 i:12585441 87 milliseconds
; ...
; 1111110000000000000000000000000000000000000000000 i:13983816 95 milliseconds
Edit: NBP_PB C Backend optimized

Re: Bit Shifting

Posted: Thu Feb 09, 2023 3:59 pm
by interfind
NicTheQuick wrote: Tue Feb 07, 2023 4:14 pm I can only imagine you mean something like this:

Code: Select all

EnableExplicit

Procedure highestBit(i.i)
    i | (i >>  1)
    i | (i >>  2)
    i | (i >>  4)
    i | (i >>  8)
    i | (i >> 16)
    ProcedureReturn i & ~(i >> 1)
EndProcedure

Define a = %100011111
Define hb

While a
	Debug RSet(Bin(a), 32, "0")
	hb = highestBit(a)
	a = ((hb << 1) | (a & (hb -1))) & ($ffffffff)
Wend
But there are also ASM instructions which can return the highest bit in O(1) instead of writing an extra procedure for that. I just don't know how to use them.
This code is nearly what i'm looking for.
Only one thing i miss.

If the highestbit is on the last left position , the next bit must go 1 to left and the highest bit
must go behind this bit, and then walk to max left again. and so on and so on.

; 000000001111
;100000000111
;000000011011
;100000001011
;000000110011 and so on

Re: Bit Shifting

Posted: Sat Feb 11, 2023 5:13 pm
by interfind
Hello again,

here is a slow Procedure permutation recursive example
of that "bit shift sequence" what i need.

But in Assembler and like that Procedure NBP_PB
for a max speed.

Code: Select all

XIncludeFile "time.pbi"
initTime(10000)

Procedure NBP_PB(v) ;Next Bit Permutation
  
  highestBit.i
  !BSF rcx, [p.v_v]           ;BitScanForward
  !MOV [p.v_highestBit], rcx  ;rcx = highestBit in v
  
  t = v | (v - 1)
  v = (t + 1) | (((~t & -~t) - 1) >> (highestBit + 1))
  
  ProcedureReturn v
  
EndProcedure


Procedure permutation(ones, zeroes, bits.s)

If zeroes = 0
  For j=0 To ones-1
    bits + "1"
  Next j

    Debug ReverseString(bits) + "   (" + Val("%"+ReverseString(bits))+ ")"

    ProcedureReturn

  Else

 If ones = 0
  For i=0 To zeroes-1
    bits + "0"
  Next i

    Debug ReverseString(bits) + "   (" + Val("%"+ReverseString(bits)) + ")"

    ProcedureReturn

  EndIf

EndIf


permutation (ones - 1, zeroes, bits + "1")

permutation (ones, zeroes - 1, bits + "0")

  ProcedureReturn
EndProcedure



StartTime = getTime()

permutation(6, 49, "")

CountTime$=StrD((getTime()-StartTime)/10000) + " Sekunden"

MessageRequester("Result", CountTime$)
All times are UTC+01:00
Page 2 of 3

Powered by phpBB® Forum Software © phpBB Limited