Ein einziges Bit zählen

[7x7]

Hi Leute,

als Bedingung für weitere Berechnungun muss ich ein 64-Bit-Register darauf hin überprüfen, ob insgesamt NUR EIN EINZIGES Bit gesetzt ist. Das ganze soll natürlich so schnell wie möglich geschehen, d.h. mit so wenig wie möglichen Taktzyklen (und natürlich in ASM). Prinzipielle Lösungsvorschläge auch gerne in Basic.

Hat da jemand eine Idee?

[NicTheQuick]

Wie wäre es damit:

Code: Alles auswählen

Macro IsOnlyOneBitSet(x)
	Bool(x = (x & (-x)) And x)
EndMacro

Define.q value = 1
Define.i a

Debug "Nur ein Bit"
For i = 0 To 63
	value = 1 << i
	Debug RSet(Bin(value), 64, "0") + " -> " + Str(IsOnlyOneBitSet(value))
Next

Debug "Ein oder zwei Bit"
For i = 0 To 63
	value = (1 << i) | (1 << Random(63, 0))
	Debug RSet(Bin(value), 64, "0") + " -> " + Str(IsOnlyOneBitSet(value))
Next

Debug "value = 0"
value = 0
Debug RSet(Bin(value), 64, "0") + " -> " + Str(IsOnlyOneBitSet(value))

[STARGÅTE]

Mein Vorschlag:

Code: Alles auswählen

Procedure OneBit(Quad.q)
	! MOV rax, [p.v_Quad]
	! BSR rcx, rax
	! MOV rdx, 1
	! SHL rdx, cl
	! CMP rdx, rax
	! JE  ll_onebit_true
	ProcedureReturn #False
	True:
	ProcedureReturn #True
EndProcedure

Debug OneBit(%00001)
Debug OneBit(%00010)
Debug OneBit(%01000)
Debug OneBit(%00000)
Debug OneBit(%01100)
Debug OneBit(%01001)

[Thorium]

Seid SSE4 gibts ja auch noch die POPCNT instruction, welche die gesetzten Bits eines Registers zählt.
Könnte aber sogar langsamer sein als Stargates Lösung für diesen speziellen Fall.

[Thorium]

Code: Alles auswählen

;Testwert festlegen
!mov rdx, 1

;bits zählen und entsprechend verzweigen
!popcnt rax, rdx
!test rax, 1
!jz NotOnlyOneBitSet

!OneBitSet:
Debug "1 Bit ist gesetzt"
End

!NotOnlyOneBitSet:
Debug "Mehrere oder kein Bit sind gesetzt."
End

Das wäre mit POPCNT.
Die Verzweigung direkt in ASM, ich denke das da noch mehr in ASM dann dahinter hängt. In ner PB-Schleife würde die Performance von der Bitauswertung warscheinlich untergehen. Vorallem wenns ne Prozedur ist.

[Helle]

POPCNT war auch mein erster Gedanke, aber dann wars mir doch zu modern ...
Hier eine übersichtliche PB-Version:

Code: Alles auswählen

Procedure OneBit(Quad.q)
  X.q = $8000000000000000
  If Quad = 0
    ProcedureReturn #False
   ElseIf X % Quad 
    ProcedureReturn #False
   Else
    ProcedureReturn #True
  EndIf 
EndProcedure

Debug OneBit(%00001)
Debug OneBit(%00010)
Debug OneBit(%01000)
Debug OneBit(%00000)
Debug OneBit(%01100)
Debug OneBit(%01001)

Idee dahinter: $8000000000000000 ist der höchste 1-Bit-Wert für ein 64-Bit-Register. Nur bei einer Division durch einen anderen 1-Bit-Wert bleibt kein Divisions-Rest (Modulo).
Klugscheiß an:
Aufpassen bei BSR: Hat der Quell-Operand den Wert Null, wird der Ziel-Operand nicht verändert; er behält seinen (zufälligen) Wert! Geht oben gut, kann aber in anderen Fällen zu bösen Fehlern führen.
Klugscheiß aus

Gruß
Helle

[NicTheQuick]

Also Macro könnte man bei dir dann auch diese Kurzfassung nutzen:

Code: Alles auswählen

Macro IsOnlyOneBitSet(x)
	Bool(x And $8000000000000000 % x = 0)
EndMacro

Wenn ich mir den ASM-Output von diesem Code hier ansehe

Code: Alles auswählen

Macro IsOnlyOneBitSet(x)
	Bool(x And $8000000000000000 % x = 0)
EndMacro

Define.q value = 1
Define.i a

a = Bool(x And $8000000000000000 % x = 0)
a = Bool(x = (x & (-x)) And x)

dann wundern mich imme Zeilen wie diese:

Code: Alles auswählen

...
  AND    r15,r15
...
  XOR    rax,rax
...
  AND    rax,rax
...
  XOR    rax,rax
...
usw.

Warum werden da Dinge mit sich selbst verUNDet oder verXORt? Hat das einen Sinn?
Hier er komplette ASM-Output:

Code: Alles auswählen

; 
; PureBasic 5.31 (Linux - x64) - generated code
; 
; (c) 2014 Fantaisie Software
; 
; The header must remain intact for Re-Assembly
; 
; :System
; :Import
; 
format ELF64
; 
extrn memset
extrn exit
; 
public PB_MemoryBase
public PB_ArgC
public PB_ArgV

macro pb_public symbol
{
  public  symbol
_#symbol:
symbol:
}


extrn SYS_InitPureBasic


section '.text' executable align 4096

public main
main:

  MOV    [PB_InitialStackValue],rsp
  SUB    rsp,40
  MOV    [PB_ArgC],edi
  MOV    [PB_ArgV],rsi
  CALL   SYS_InitPureBasic
; Macro IsOnlyOneBitSet(x)
; 
; Define.q value = 1
  MOV    qword [v_value],1
; Define.i a
; 
; a = Bool(x And $8000000000000000 % x = 0)
  CMP    qword [v_x],0
  JE     No0
  MOV    r15,qword [v_x]
  MOV    rax,-9223372036854775808
  CQO
  IDIV   r15
  MOV    r15,rdx
  AND    r15,r15
  JNE    No0
Ok0:
  MOV    rax,1
  JMP    End0
No0:
  XOR    rax,rax
End0:
_Bool0:
  AND    rax,rax
  JE    .False
  MOV    rax,1
  JMP   .True
.False:
  XOR    rax,rax
.True:
  MOV    qword [v_a],rax
; a = Bool(x = (x & (-x)) And x)
  MOV    r15,qword [v_x]
  MOV    r14,qword [v_x]
  MOV    r13,qword [v_x]
  NEG    r13
  AND    r14,r13
  CMP    r15,r14
  JNE    No1
  CMP    qword [v_x],0
  JE     No1
Ok1:
  MOV    rax,1
  JMP    End1
No1:
  XOR    rax,rax
End1:
_Bool1:
  AND    rax,rax
  JE    .False
  MOV    rax,1
  JMP   .True
.False:
  XOR    rax,rax
.True:
  MOV    qword [v_a],rax
_PB_EOP:
_PB_EOP_NoValue:
  CALL   PB_EndFunctions
  MOV    rsp,[PB_InitialStackValue]
  MOV    rdi,[PB_ExitCode]
  CALL   exit
PB_EndFunctions:
  SUB    rsp,40
  ADD    rsp,40
  RET

section '.data' writeable
pb_public PB_DEBUGGER_LineNumber
  dd     -1
pb_public PB_DEBUGGER_IncludedFiles
  dd     0
pb_public PB_DEBUGGER_FileName
  db     0
pb_public PB_Compiler_Unicode
  dd     0
pb_public PB_Compiler_Thread
  dd     0
pb_public PB_Compiler_Purifier
  dd     0
pb_public PB_Compiler_Debugger
  dd     0
align 8
align 8
align 8
s_s:
  dq     0
  dq     -1
align 8

_PB_BSSSection:
align 8

I_BSSStart:
PB_MemoryBase:  rq 1
PB_ArgC:  rd 1
PB_ArgV:  rq 1
PB_ExitCode:  rq 1
PB_InitialStackValue:  rq 1
align 8
v_value rq 1
PB_DataPointer rq 1
v_a rq 1
v_x rq 1
align 8
align 8
align 8
align 8
I_BSSEnd:
section '.text' executable align 4096
section '.data' writeable
SYS_EndDataSection:

[Helle]

AND rax,rax: Wenn rax=0 wird das Zero-Flag gesetzt, sonst gelöscht. Entspricht also CMP rax,0. (Auch OR rax,rax usw.). Beim nachfolgenden bedingten Sprung wird dann das Zero-Flag ausgewertet (JNE=JNZ oder JE=JZ macht es vielleicht deutlicher).
XOR rax,rax: Setzt rax auf Null. Entspricht MOV rax,0.

[Thorium]

Edit: Helle war schneller.

Wenn man eine Zahl mit sich selbst "xort", kommt Null raus. Das ist der effektivste Weg ein Register zu nullen. Ist schneller als "mov reg,0", bzw ist eine kleinere Instruktion.
Warum man ne Zahl mit sich selbst "andet" ist mir aber nicht klar.

[NicTheQuick]

*facepalm*
Das mit XOR hätte mir eigentlich klar sein müssen. Ich hab das sogar vor Jahren ebenfalls schon so gemacht.

Aber das mit den Zero-Flag ist toll. Danke!