Bit Shifting

Bare metal programming in PureBasic, for experienced users
interfind
User
User
Posts: 22
Joined: Thu Apr 22, 2021 1:41 pm

Re: Bit Shifting

Post 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
User avatar
mk-soft
Always Here
Always Here
Posts: 5335
Joined: Fri May 12, 2006 6:51 pm
Location: Germany

Re: Bit Shifting

Post by mk-soft »

A old project from me, no c-backend ...

Link: Bitshift and Rotation
My Projects ThreadToGUI / OOP-BaseClass / EventDesigner V3
PB v3.30 / v5.75 - OS Mac Mini OSX 10.xx - VM Window Pro / Linux Ubuntu
Downloads on my Webspace / OneDrive
User avatar
NicTheQuick
Addict
Addict
Posts: 1224
Joined: Sun Jun 22, 2003 7:43 pm
Location: Germany, Saarbrücken
Contact:

Re: Bit Shifting

Post 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.
The english grammar is freeware, you can use it freely - But it's not Open Source, i.e. you can not change it or publish it in altered way.
interfind
User
User
Posts: 22
Joined: Thu Apr 22, 2021 1:41 pm

Re: Bit Shifting

Post 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.
User avatar
idle
Always Here
Always Here
Posts: 5042
Joined: Fri Sep 21, 2007 5:52 am
Location: New Zealand

Re: Bit Shifting

Post by idle »

what is the goal of this, what are you wanting to do?
juergenkulow
Enthusiast
Enthusiast
Posts: 544
Joined: Wed Sep 25, 2019 10:18 am

Re: Bit Shifting

Post 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
interfind
User
User
Posts: 22
Joined: Thu Apr 22, 2021 1:41 pm

Re: Bit Shifting

Post 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.
interfind
User
User
Posts: 22
Joined: Thu Apr 22, 2021 1:41 pm

Re: Bit Shifting

Post 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. :)
interfind
User
User
Posts: 22
Joined: Thu Apr 22, 2021 1:41 pm

Re: Bit Shifting

Post 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"))
User avatar
SPH
Enthusiast
Enthusiast
Posts: 268
Joined: Tue Jan 04, 2011 6:21 pm

Re: Bit Shifting

Post by SPH »

very confused this post
http://HexaScrabble.com/
!i!i!i!i!i!i!i!i!i!
!i!i!i!i!i!i!
!i!i!i!
//// Informations ////
Portable LENOVO ideapad 110-17ACL 64 bits
Version de PB : 5.73LTS - 32 bits
User avatar
Caronte3D
Addict
Addict
Posts: 1027
Joined: Fri Jan 22, 2016 5:33 pm
Location: Some Universe

Re: Bit Shifting

Post 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?
User avatar
idle
Always Here
Always Here
Posts: 5042
Joined: Fri Sep 21, 2007 5:52 am
Location: New Zealand

Re: Bit Shifting

Post 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.
juergenkulow
Enthusiast
Enthusiast
Posts: 544
Joined: Wed Sep 25, 2019 10:18 am

Re: Bit Shifting

Post 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
Last edited by juergenkulow on Fri Feb 10, 2023 5:35 am, edited 1 time in total.
interfind
User
User
Posts: 22
Joined: Thu Apr 22, 2021 1:41 pm

Re: Bit Shifting

Post 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
interfind
User
User
Posts: 22
Joined: Thu Apr 22, 2021 1:41 pm

Re: Bit Shifting

Post 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$)

Post Reply