Bit Shifting

[juergenkulow]

@interfind
Why? What is the benefit of this programme code?

[interfind]

Bitwise compare of Values

[Demivec]

Here's my version with assembly only for BSR():

Code: Select all

EnableExplicit

;bit scan reverse - macro usable only inside a procedure
; _x_ is name of input variable holding value
; _hb_ is name of output variable holding location of highest bit
Macro mp_bsr(_v_, _hb_)
  !BSR rcx, [p.v_#_v_] ;BitScanReverse
  !MOV [p.v_#_hb_], rcx ;rcx = highestBit in _v_
EndMacro

Procedure.q bperm(bitCount, setBits, n = 0)
  ;n = current bit permutation, set to 0 to get first permutation
  ;bitCount = number of bits being used, {0 < bitCount <= SizeOf(integer) * 8}
  ;setBits = number of 'one' bits or bits set, {0 <= setBits <= (SizeOf(integer) * 8) - 1}
  ;Returns next bit permutation or 0 if n = highest bit permutation
  
  ;Two reference bit patterns are operated on, they are patterns #1 ('fhzzzLrr') and #2 ('zzzzzLrr')
  ; Only bits 0 to bitCount are ever used as part of a permuation.
  ; f = flag bit
  ; h = all highest set bits next to and including flag bit f
  ; z = all zero bits between highest set bits and next set bit L
  ; L = low set bit (first set bit after first zero bit)
  ; r = remaining bits that will be left unchanged
  ; All bit counting is from the least significant bit #0. 'First' means highest or leftmost bit.

  Protected.i flagBit, temp, p0, p1, highSetBitCount
  
  If setBits <= 0 Or (bitCount <= 0) Or (bitCount > SizeOf(integer) * 8) Or (setBits > bitCount)
    ProcedureReturn -1 ;error
  EndIf
  
  If n = 0
    ProcedureReturn (1 << setBits) - 1;return starting permutation
  EndIf
  
  
  flagBit = 1 << (bitCount - 1) ;highest bit value needed or used
  If n & flagBit
    ;operating on reference bit pattern #1, 'fhzzzLrr' 
    temp = ~n & ((flagBit - 1 + flagBit)) ;mask, makes sure to remove excessive high bits (only need bits 0 - (bitCount - 1))
    mp_bsr(temp, p0) ;position of highest bit set to 0 (the first z in reference pattern)
    highSetBitCount = bitCount - p0 - 1 ;count of high bits set to 1 (the f and all h bits)
    
    If highSetBitCount = setBits
      ProcedureReturn 0 ;signal max permutation already reached
    EndIf
    
    temp = n & ((1 << (p0 + 1)) - 1) ;mask off high bits (the f and all h bits left of first z bit in reference pattern)
    mp_bsr(temp, p1)  ;position of set bit to increment (the L bit, first set bit after first z in reference pattern)
    temp = ((1 << (highSetBitCount + 1)) - 1) << (p1 + 1) ;new repositioned block of set counter bits (first h bits + new L bit)
    
    ProcedureReturn (n & ((1 << p1) - 1)) | temp ;(combine r bits with new block of counter bits)
    
  Else
    ;operating on reference bit pattern #2, 'zzzzzLrr'
    mp_bsr(n, p1) ;position of highest bit set to 1 (the L bit in reference pattern)
    ProcedureReturn   n + (1 << p1) ;(add value to highest set bit to exchange bits at positions p1 and p1 + 1)
  EndIf
EndProcedure

Define StartTime, CountTime$, t1.d
Define my_perm, size = 55, set = 6 ;size = 8, set = 3 
StartTime = ElapsedMilliseconds()

my_perm = bperm(size, set) ;start 
Repeat
  Debug "" + RSet(Bin(my_perm), size, "0") + "   (" + my_perm + ")"
  my_perm = bperm(size, set, my_perm)
Until my_perm = 0

t1 = (ElapsedMilliseconds() - StartTime) / 1000 
CountTime$= "t1 = " + StrD(t1) + " Seconds"
MessageRequester("Result", CountTime$)

@interfind: It's about 320+ times faster than your version. For your example of 55 bits with 6 ones and 49 zeroes it computes the 55!/(49!*6!) = 28989675 permutations in 0.152 seconds on my machine. It should be easy to convert to all assembly but I'll leave that for you to do. I just did the bit twiddling. I haven't fully error tested it with max values, error inputs or with x86 compilation. I have only tested it with x64 bit. Everything is documented so that anyone can hopefully follow the operations with onlt a little effort and some familiarity with the bit operators.

I don't know yet of a method to compute the xth lexographical ordered permutation without going through all the previous permutations. The routine above simply returns the next lexographically ordered permutation given the current one as a pattern of bits in a quad value.

I am curious why you want or need the permutations ordered in the way you have requested instead of the way the routine you found does it.

[interfind]

Hello Demivec,

thank you very very much for the brilliant Source you have made.
This was exactly what i want.
It's amazing what all is possible with so called bit twiddling.

I have try to convert the routine to assembly,
Can you take a look on it and check for some optimization or errors please.

Code: Select all

[size=50]EnableExplicit
;DisableDebugger

Global result.i

Macro mp_bsr(_v_, _hb_)
  !BSR rcx, [p.v_#_v_] ;BitScanReverse
  !MOV [p.v_#_hb_], rcx ;rcx = highestBit in _v_
EndMacro


Procedure.q bperm(bitCount, setBits, n = 0)
  EnableASM
  ;Protected.i flagBit, temp, p0, p1, highSetBitCount

  ;If setBits <= 0 Or (bitCount <= 0) Or (bitCount > SizeOf(integer) * 8) Or (setBits > bitCount)
  ;  ProcedureReturn -1 ;error
  ;EndIf
  !CMP qword [p.v_setBits], 0
  !JLE error
  !CMP qword [p.v_bitCount], 0
  !JLE error
  !CMP qword [p.v_bitCount], 64 ;SizeOf(integer)
  !JG error
  !MOV rax, [p.v_setBits]
  !CMP rax, [p.v_bitCount]
  !JG error

  ;If n = 0
  ;  ProcedureReturn (1 << setBits) - 1 ;return starting permutation
  ;EndIf
  !CMP qword [p.v_n], 0
  !JNE start
  !MOV rcx, [p.v_setBits]
  !MOV rax, 1
  !SHL rax, cl
  !DEC rax
  ProcedureReturn

  ;flagBit = 1 << (bitCount - 1) ;highest bit value needed or used
!start:  
  !MOV rcx, [p.v_bitCount]
  !DEC rcx
  !MOV rdx, rcx
  !MOV rax, 1
  !SHL rax, cl

  ;If n & flagBit
  !MOV r8, [p.v_n]
  !MOV r10, r8
  !TEST r8, rax
  !JZ nextbit

  ;temp = ~n & ((flagBit - 1 + flagBit)) ;mask, makes sure to remove excessive high bits (only need bits 0 - (bitCount - 1))
  !LEA rax, [rax-1+rax]
  !NOT r10
  !AND r10, rax

  ;mp_bsr(temp, p0)   ;position of highest bit set to 0 (the first z in reference pattern)
  !BSR r9, r10

  ;highSetBitCount = bitCount - p0 - 1 ;count of high bits set to 1 (the f and all h bits)
  !SUB rdx, r9
  
  ;If highSetBitCount = setBits
    ;ProcedureReturn 0 ;signal max permutation already reached
  ;EndIf
  !cmp rdx, [p.v_setBits]
  !JZ maxpermu

  ;temp = n & ((1 << (p0 + 1)) - 1) ;mask off high bits (the f and all h bits left of first z bit in reference pattern)
  !MOV r10, r8
  !MOV rax, 1
  !INC r9
  !MOV rcx, r9
  !SHL rax, cl
  !DEC rax
  !AND r10, rax

  ;mp_bsr(temp, p1)  ;position of set bit to increment (the L bit, first set bit after first z in reference pattern)
  !BSR r9, r10

  ;temp = ((1 << (highSetBitCount + 1)) - 1) << (p1 + 1) ;new repositioned block of set counter bits (first h bits + new L bit)
  !MOV rax, 1
  !INC rdx
  !MOV rcx, rdx
  !SHL rax, cl
  !DEC rax
  !MOV rcx, r9
  !INC rcx
  !SHL rax, cl

  ;ProcedureReturn (n & ((1 << p1) - 1)) | temp ;(combine r bits with new block of counter bits)
  !MOV rdx, 1
  !MOV rcx, r9
  !SHL rdx, cl
  !DEC rdx
  !AND r8, rdx
  !OR rax, r8
  ProcedureReturn

  ;Else
!nextbit:
  ;mp_bsr(n, p1) ;position of highest bit set to 1 (the L bit in reference pattern)
  !BSR rcx, r8

  ;n + (1 << p1)
  !MOV rax, 1
  !SHL rax, cl
  !ADD rax, r8
  ProcedureReturn
  
!maxpermu:
  ProcedureReturn 0
  
!error:
  ProcedureReturn -1
  ;EndIf
  DisableASM 
EndProcedure


Define StartTime, CountTime$, t1.d
Define my_perm, size = 49, set = 6
Define index

StartTime = ElapsedMilliseconds()
index = 0
my_perm = bperm(size, set) ;start
Repeat
  Debug "" + RSet(Bin(my_perm), size, "0") + "   (" + my_perm + ")"
  my_perm = bperm(size, set, my_perm)
  index+1  
Until my_perm = 0

t1 = (ElapsedMilliseconds() - StartTime) / 1000
CountTime$= "t1 = " + StrD(t1) + " Seconds"

MessageRequester("Result", CountTime$ + #LF$ + "Permutations: " + index)