Index vom x-tem gesetztem Bit

[calibra301]

Hallo,

hab irgendwie Gehirnblockade...

Ich habe hier einen Binärwert von z.B. 00101010

Möchte nun die Position des z.B. 3. gesetzten Bit ermitteln.
Wäre in diesem Fall der Wert 32

Kann aber auch sein das ich das 5. gesetzte Bit suche, also von rechts nach links durchschauen
und dann rechts wieder anfangen. Wäre dann also der Wert 8.

Kriege das aber schleifentechnisch irgendwie nicht "schön" verpackt.
Nach XX Stunden glotzen auf den eigenen Code Blödsinn schaltet dann auch das Hirn ab :-)

Gruss
Calli

[himitsu]

Was ist an der Schleife so schwer?

schauen ob LSB gesetzt ist (Odd)
wenn nicht, dann Shift rechts und erneut nachsehen. (dabei mitzählen wie oft)

Wenn Durchläufe größer Bitanzahl, dann abbrechen. Ober besser schon vorher nachsehn ob Wert<>0 (mindestens ein Bit vorhanden).

[Andreas13]

Zitat:

Zitat von himitsu (Beitrag 1466029)

Was ist an der Schleife so schwer?
... schauen ob ÖSB gesetzt ist (Odd)

Sorry Himitsu, aber was meinst Du mit ÖSB?
Gruß, Andreas

[arnold mueller]

Er meint LSB und hat das L nicht getroffen.

LSB ist das niederwertigste Bit, also das ganz rechts.

[Aviator]

LSB bedeutet übrigens Least Significant Bit.

So in der Art könntest du das evtl. umsetzen. Der Code ist ungetestet. Hoffentlich tut er trotzdem was er soll oder gibt dir zumindest einen Anstoß wie du es lösen kannst. Die Funktion gibt -1 zurück wenn das Bit mit der gesuchten Position nicht gefunden wurde.

Delphi-Quellcode:

function CheckBit(const Value: Integer; BitNumber: Integer) : Integer;
var
  i: Integer;
begin
  Result := -1;
  i := 0;
  
  while (Value > 0) do begin
    if (Value and $01) then begin
      if (i = BitNumber) then begin
        Result := i;
        Break;
      end;
      Inc(i);
    end;
  end;
end;

[samso]

Den Vorschlag von Aviator aufgenommen und erweitert:

Delphi-Quellcode:

program Project5;

{$APPTYPE CONSOLE}
{$R *.res}

uses
  System.SysUtils;

function CheckBit(const Value, BitNumber: Integer): Integer;
var
  i: Integer;
  Mask: Integer;
begin
  if (Value <> 0) then
  begin
    i := 0;
    Mask := 0;
    while true do
    begin
      if Mask = 0 then
        Mask := 1;
      if (Value and Mask) <> 0 then
      begin
        Inc(i);
        if (i = BitNumber) then
        begin
          Result := Mask;
          Break;
        end;
      end;
      Mask := Mask shl 1;
    end;
  end
  else
    Result := -1;
end;

begin
  try
    if CheckBit($2A, 3) = 32 then
      writeln('Test 1 - ok');
    if CheckBit($2A, 5) = 8 then
      writeln('Test 2 - ok');
    readln;
  except
    on E: Exception do
      writeln(E.ClassName, ': ', E.Message);
  end;
end.

[himitsu]

Zitat:

Delphi-Quellcode:

Mask := 0;
...
if Mask = 0 then
  Mask := 1;

Warum nicht gleich richtig initialisieren? (

Delphi-Quellcode:

:= 1;

)

Und was die doppelte Prüfung soll, hab ich nicht verstanden.
Denn aus

Delphi-Quellcode:

if CheckBit($2A, 5) = 32 then

wird

Delphi-Quellcode:

if $2A and (1 shl 5) = 32 then

, (wenn ich den Inhalt deiner Funktion wegoptimiere und den Fall "Bit nicht gesetzt" igonriere, da er für dieses IF egal ist)
obwohl

Delphi-Quellcode:

if $2A and (1 shl 5) <> 0 then

, bzw

Delphi-Quellcode:

if $2A and 32 <> 0 then

ausreicht,
oder einfach nur

Delphi-Quellcode:

if Ord($2A shr 5) then

.



Das Beispiel genommen und alles überflüssige rausgeworfen, da sich dieses Problem mit binärer Mathemaik lösen lässt.

Delphi-Quellcode:

function CheckBit(const Value, BitNumber: Integer): Boolean; inline;
begin
  Result := Ord(Value shr BitNumber);  //Result := (Value shr BitNumber) and $01 <> 0;
end;

oder (für Alle, die lieber links als rechts sind)

Delphi-Quellcode:

function CheckBit(const Value, BitNumber: Integer): Boolean; inline;
begin
  Result := Value and (1 shl BitNumber) <> 0;
end;

OK, mathematisch geht auch

Delphi-Quellcode:

function CheckBit(const Value, BitNumber: Integer): Boolean; inline;
begin
  Result := Value and Round(IntPower(2, BitNumber)) <> 0;
end;

function CheckBit(const Value, BitNumber: Integer): Boolean; inline;
begin
  Result := (Value div Round(IntPower(2, BitNumber))) and $01 <> 0;
end;

PS:

Delphi-Quellcode:

function KleinstesBit(Value: Integer): Integer;
begin
  if Value = 0 then
    Exit(-1);
  Result := 0;
  while not Odd(Value) do begin
    Inc(Result);
    Value := Value shr 1;
  end;
end;

[samso]

Zitat:

Zitat von himitsu (Beitrag 1466086)

Und was die doppelte Prüfung soll, hab ich nicht verstanden.

Ja, dass sehe ich. Das ist die Überprüfung der Vorgaben des Thread-Erstellers. Er schreibt:

"Möchte nun die Position des z.B. 3. gesetzten Bit ermitteln. Wäre in diesem Fall der Wert 32"

Das entspricht dem Test 1.

Er schreibt:
"Kann aber auch sein das ich das 5. gesetzte Bit suche, also von rechts nach links durchschauen
und dann rechts wieder anfangen. Wäre dann also der Wert 8."

Das entspricht dem Test 2.

Deine Lösung erfüllt die Vorgaben nicht.

[Maekkelrajter]

Zitat:

Zitat von samso (Beitrag 1466090)

Ja, dass sehe ich. Das ist die Überprüfung der Vorgaben des Thread-Erstellers. Er schreibt:

"Möchte nun die Position des z.B. 3. gesetzten Bit ermitteln. Wäre in diesem Fall der Wert 32"

Das entspricht dem Test 1.

Er schreibt:
"Kann aber auch sein das ich das 5. gesetzte Bit suche, also von rechts nach links durchschauen
und dann rechts wieder anfangen. Wäre dann also der Wert 8."

Das entspricht dem Test 2.

Deine Lösung erfüllt die Vorgaben nicht.

Es ist aber auch nicht so leicht zu verstehen, was der TE tatsächlich erreichen möchte. Ich habe das so verstanden, dass er die Bitmaske sucht, die ein einziges gesetztes Bit an einer bestimmten Stelle hat. Das 3. Bit (von links!) in '00101010' wäre demnach '00100000', also dezimal 32, aber nur, wenn es sich bei dem Binärwert, wie in dem Beispiel, tatsächlich um ein Byte handelt. Deshalb ist eigentlich nur die Zählung von rechts nach links sinnvoll. Da spielt es bekanntlich keine Rolle, welcher Integer-Datentyp für den Binärwert verwendet wird, d. h. wie viele Stellen die Binärzahl hat
Meine Lösung:

Delphi-Quellcode:

Function Bitmask(Value: Byte; Position: Integer; FromLeft: Boolean = true): Byte;
  var i,len: Integer;
      mask: Byte;  
begin
  result:= 0;
  len:= (sizeof(value) * 8);    // Anzahl der Bits
  If FromLeft Then Position:= (len - position) + 1;
  for i:= 0 to len - 1 do
  begin
    mask:= (1 shl i);
    If (position = i+1) and (value and mask <> 0) Then
    begin
      result:= mask;
      break;
    end;
  end;
end;


Procedure ShowBitmask;
var
  mask: Byte;
begin
  mask := Bitmask(42,3,true);
  Showmessage('Bitmask = ' + inttostr(mask));  // zeigt "Bitmask = 32"
end;

Dabei kann die Zählung wahlweise von links oder von rechts erfolgen, indem der (optionale) Boolean - Parameter 'FromLeft' auf 'True' (Vorgabe) oder 'False' gesetzt wird.
Der Rückgabewert ist der Dezimalwert der Bitmaske.
Ich bin allerdings immer noch nicht ganz sicher, ob das wirklich die Lösung ist, die der TE sucht :(

[calibra301]

Danke !
Das Brett vorm Kopf ist weg.

Meine Formulierung war aber wohl auch etwas unverständlich. Der Hintergrund ist
schwer zu erklären.
Beispiel: 42 = Binär 00101010, suche das fünfte gesetzte Bit von rechts.
Sind ja nur 3 Bit gesetzt also vorne wieder anfangen.
Ergebnis wäre dann 8

Delphi-Quellcode:

Function Bitmask(Value: Word; Position: Integer; FromLeft: Boolean = true): Byte;
var i,len: Integer;
     mask: Byte;
    Bitcounter:byte;
begin
  result:= 0;
  Bitcounter:=0;
  len:= (sizeof(value) * 8); // Anzahl der Bits
  If FromLeft Then Position:= (len - position) + 1;
  while Bitcounter<>Position do
  Begin
    for i:= 0 to len - 1 do
    begin
      mask:= (1 shl i);
      If value and mask <> 0 Then Bitcounter:=Bitcounter+1;
      if Bitcounter=Position then
      Begin
       result:=Mask;
       break;
      end;
    end;
  End;

end;


procedure TForm1.Button1Click(Sender: TObject);
var
  mask: Byte;
begin
  mask := Bitmask(42,5,false);
  Showmessage('Das '+inttostr(5)+'. Bit ist an Stelle ' + inttostr(mask)); // zeigt "Bitmask = 32"
end;

Das war so einer Dieser Tage wo man die Kiste einfach hätte abstellen sollen...

Noch mal Danke !
Calli

[TBx]

Magst Du uns einmal darüber aufklären, wofür Du diese Funktion brauchst?
Mir fällt da so spontan kein Anwendungsfall für ein.

[Uwe Raabe]

Probier mal

Delphi-Quellcode:

mask := Bitmask(0,5,false);

[Maekkelrajter]

Zitat:

Zitat von calibra301 (Beitrag 1466134)

Beispiel: 42 = Binär 00101010, suche das fünfte gesetzte Bit von rechts.
Sind ja nur 3 Bit gesetzt also vorne wieder anfangen.
Ergebnis wäre dann 8

Ah jetzt ja! :idea: Jetzt habe ich wohl endlich verstanden, was du meinst mit: suche das fünfte gesetzte Bit von rechts
Dann kann man die Funktion aber auch deutlich vereinfachen: Der Unfug mit dem 'Richtungswechsel' kann entfallen und es können 32-Bit Parameter und Variablen verwendet werden.
Und Uwe Raabes Hinweis ist auch berücksichtigt. :wink:

Delphi-Quellcode:

Function Bitmask(Value,Position: cardinal):cardinal;
var i,len: Integer;
     mask, Bitcounter: Cardinal;
begin
  result:= 0;
  If value <> 0 Then
  begin
    Bitcounter:= 0;
    len:= (sizeof(value) * 8); // Anzahl der Bits
    while Bitcounter <> Position do
    begin
      for i:= 0 to len - 1 do
      begin
        mask:= (1 shl i);
        If value and mask <> 0 Then inc(Bitcounter);
        if Bitcounter = Position then
        begin
          result:= Mask;
          break;
        end;
      end;
    end;
  end;
end;


procedure TForm1.Button1Click(Sender: TObject);
var
  mask: Byte;
begin
  mask := Bitmask(42,5);
  Showmessage('Das '+inttostr(5)+'. Bit ist an Stelle ' + inttostr(mask));
end;

Auch ich grüble allerdings schon die ganze Zeit über die Frage, wozu das Ganze gut sein soll?? :shock:

Gruß LP

[Uwe Raabe]

Ich will auch mal:

Delphi-Quellcode:

Function Bitmask(Value, Position: Cardinal): Cardinal;
var
  i: Integer;
  Bitcounter: Cardinal;
  valSet: TIntegerSet;
begin
  result := 0;
  valSet := TIntegerSet(Value);
  If valSet <> [] Then
  begin
    Bitcounter := 0;
    while Bitcounter < Position do
    begin
      for i in valSet do
      begin
        inc(Bitcounter);
        if Bitcounter = Position then
          Exit(1 shl i);
      end;
    end;
  end;
end;

[Uwe Raabe]

Und hier noch eine etwas veränderte Version für Delphi 10.4:

Delphi-Quellcode:

Function Bitmask(Value, Position: Cardinal): Cardinal;
var
  i: Integer;
  Bitcounter: Cardinal;
  cntOfBitsSet: Integer;
  valSet: TIntegerSet;
begin
  result := 0;
  cntOfBitsSet := CountPopulation32(value);
  If (cntOfBitsSet > 0) and (Position > 0) Then
  begin
    if cntOfBitsSet < Position then
      Position := ((Position - 1) mod cntOfBitsSet) + 1;
    valSet := TIntegerSet(Value);
    Bitcounter := Position;
    for i in valSet do
    begin
      dec(Bitcounter);
      if Bitcounter = 0 then
        Exit(1 shl i);
    end;
  end;
end;

[Maekkelrajter]

Chapeau!
So sieht der Unterschied zwischen einem 'Master Developer' und einem dilettierenden Autodidakten aus! :oops:

Erst vor ein paar Jahren, als wieder kostenlose Delphi-Versionen verfügbar waren, hatte ich den Schritt von Delphi 4 zu Delphi 10 gewagt. Alle die schönen Features der modernen Delphi-Versionen, die die Arbeit erleichtern und effizienteren, kompakteren oder auch eleganteren Programmcode ermöglichen, finde ich leider meistens nur per Zufall oder eben durch Beispiele (s. o.)

Gruß LP

[einbeliebigername]

Hallo,

ich will auch mitspielen. Habe gleich zwei Varianten. Leider kennt Delphi die Operatoren ROL und ROR nicht. Ich glaube Pascal hatte die.

Delphi-Quellcode:

program Project1;

{$APPTYPE CONSOLE}

{$R *.res}

uses
  System.SysUtils;

{$IFOPT Q+}{$DEFINE OVERFLOWCHECKSON}{$ENDIF}
{$Q-}
function Rol(const aValue: Byte; const aN: Integer): Byte; //inline;
begin
  Result:= ((aValue shl (aN and 7)) and $FF) or (aValue shr (8- (aN and 7)));
end;

function Ror(const aValue: Byte; const aN: Integer): Byte; //inline;
begin
  Result:= (aValue shr (aN and 7)) or ((aValue shl (8- (aN and 7))) and $FF);
end;
{$IFDEF OVERFLOWCHECKSON}{$Q+}{$ENDIF}

function ValueOfNthSetBitV1(aValue: Byte; aN: UInt64): Byte;
begin
  if aValue= 0 then
    raise Exception.Create('Fehlermeldung');
  Result:= 0;
  while aN> 0 do
  begin
    if Result= 0 then
      Result:= 1
    else
      Result:= Rol(Result, 1);
    if aValue and 1<> 0 then
      Dec(aN);
    aValue:= Ror(aValue, 1);
  end;
end;

function ValueOfNthSetBitV2(const aValue: UInt64; const aValueBitWidth: Byte; const aN: UInt64): Byte;
var
  vTmp: Array[0..63] of UInt64;
begin
  if aValueBitWidth= 0 then
    raise Exception.Create('Fehlermeldung');
  var vBitCount: Byte := 0;
  for var vI: Integer := 0 to aValueBitWidth- 1 do
  begin
    var vBit: UInt64 := 1 shl vI;
    if (aValue and vBit)<> 0 then
    begin
      vTmp[vBitCount]:= vBit;
      Inc(vBitCount);
    end;
  end;
  if vBitCount= 0 then
    raise Exception.Create('Fehlermeldung');
  Result:= vTmp[(aN- 1) mod vBitCount];
end;

begin
  try
    WriteLn(Format('ValueOfNthSetBitV1(42, 3)= %d', [ValueOfNthSetBitV1(42, 3)]));
    WriteLn(Format('ValueOfNthSetBitV1(42, 5)= %d', [ValueOfNthSetBitV1(42, 5)]));
    WriteLn(Format('ValueOfNthSetBitV2(42, 3)= %d', [ValueOfNthSetBitV2(42, 8, 3)]));
    WriteLn(Format('ValueOfNthSetBitV2(42, 5)= %d', [ValueOfNthSetBitV2(42, 8, 5)]));
    Readln;
  except
    on E: Exception do
      Writeln(E.ClassName, ': ', E.Message);
  end;
end.

[samso]

Sehr schöne Vorschläge :-D. Bevor jetzt gleich die Lösung via Cloud-Computing kommt - back to the roots:

Delphi-Quellcode:

program Project5;

uses
  SysUtils;

function CheckBitAsm(const Value, BitNumber: Integer): Integer;
asm
  or    Value,Value
  jz    @exit
  cmp   BitNumber,0
  jle   @exit
  mov   ecx,1
@loop:
  test  Value, ecx
  jz    @next
  dec   BitNumber
  jz    @ready
@next:
  rol   ecx,1
  jmp   @loop
@ready:
  mov   eax, ecx
  ret
@exit:
  xor   eax,eax
  ret
end;

begin
  try
// Test
    if CheckBitAsm(42, 3) = 32 then
      writeln('Test 3 - ok');
    if CheckBitAsm(42, 5) = 8 then
      writeln('Test 4 - ok');
    readln;
  except
    on E: Exception do
      writeln(E.ClassName, ': ', E.Message);
  end;

Natürlich nicht ernst gemeint!

[Uwe Raabe]

Zitat:

Zitat von samso (Beitrag 1466186)

Natürlich nicht ernst gemeint!

Glück gehabt. Ich hätte sonst nämlich gleich nach den Lösungen für Win64, MacOS, Android, iOS und Linux mit ihren jeweiligen Derivaten gefragt 8-)

[Andreas13]

Zitat:

Zitat von einbeliebigername (Beitrag 1466182)

Delphi-Quellcode:

  
…
  if aValueBitWidth= 0 then
    raise Exception.Create('Fehlermeldung');
  var vBitCount: Byte := 0;
  for var vI: Integer := 0 to aValueBitWidth- 1 do
  begin
    var vBit: UInt64 := 1 shl vI;
    if (aValue and vBit)<> 0 then 
&#8230;

Sorry, aber Deine Lösung läßt sich (unter XE5) (noch?) nicht kompilieren. Sind die Variablen-Deklarationen innerhalb der For-Schleife unter XE8 schon zulässig oder sind die Zeilen nur beim Hineinkopieren verrutscht?
Danke & Gruß, Andreas

[Uwe Raabe]

Zitat:

Zitat von Andreas13 (Beitrag 1466188)

Sind die Variablen-Deklarationen innerhalb der For-Schleife unter XE8 schon zulässig oder sind die Zeilen nur beim Hineinkopieren verrutscht?

Inline-Variablen gibt es erst seit Delphi 10.3, also nein und nein.

[einbeliebigername]

Zitat:

Zitat von Andreas13 (Beitrag 1466188)

Sorry, aber Deine Lösung läßt sich (unter XE5) (noch?) nicht kompilieren.

Sorry, wollte die Inline-Variablen auch mal ausprobieren. Dann aber vergessen die wieder rauszunehmen:

Delphi-Quellcode:

function ValueOfNthSetBitV2(const aValue: UInt64; const aValueBitWidth: Byte; const aN: UInt64): Byte;
var
  vTmp: Array[0..63] of UInt64;
  vBitCount: Byte;
  vI: Integer;
  vBit: UInt64;
begin
  if aValueBitWidth= 0 then
    raise Exception.Create('Fehlermeldung');
  vBitCount:= 0;
  for vI:= 0 to aValueBitWidth- 1 do
  begin
    vBit:= 1 shl vI;
    if (aValue and vBit)<> 0 then
    begin
      vTmp[vBitCount]:= vBit;
      Inc(vBitCount);
    end;
  end;
  if vBitCount= 0 then
    raise Exception.Create('Fehlermeldung');
  Result:= vTmp[(aN- 1) mod vBitCount];
end;

[Andreas13]

Danke Uwe & einbeliebigername!
Andreas

[js747a]

Var byte1 : Byte;

If (byte1 AND 1) = 1 then ..... Bit 1 gesetzt (=1)
If (byte1 AND 2) = 2 then ..... Bit 2 gesetzt (=1)
If (byte1 AND 4) = 4 then ..... Bit 3 gesetzt (=1)
If (byte1 AND 8) = 8 then ..... Bit 4 gesetzt (=1)
If (byte1 AND 16) = 16 then ..... Bit 5 gesetzt (=1)
If (byte1 AND 32) = 32 then ..... Bit 6 gesetzt (=1)
If (byte1 AND 64) = 64 then ..... Bit 7 gesetzt (=1)
If (byte1 AND 128) = 128 then ..... Bit 8 gesetzt(=1)

[himitsu]

Delphi-Quellcode:

if byte1 and 1 = 1 then 
if byte1 and 2 = 2 then 
if byte1 and 4 = 4 then 
if byte1 and 8 = 8 then 
...

// keine Redundanzen: erstmal die unnötig doppelten Zahlen entfernt

if byte1 and 1 <> 0 then 
if byte1 and 2 <> 0 then 
if byte1 and 4 <> 0 then 
if byte1 and 8 <> 0 then 
...

// und dann gibt es noch viele andere Wege, um das letzte/rechte Bit zu prüfen

if Odd(byte1 {shr 0}) then  // if (byte1 {shr 0}) and 1 <> 0 then
if Odd(byte1 shr 1) then  // if (byte1 shr 1) and 1 <> 0 then
if Odd(byte1 shr 2) then  // if (byte1 shr 2) and 1 <> 0 then
if Odd(byte1 shr 3) then  // if (byte1 shr 3) and 1 <> 0 then
...

// oder man nutzt direkt vorhandene Bit-Operationen

//type TByteSet = set of 0..7;
if 1 in TByteSet(byte1) then 
if 2 in TByteSet(byte1) then 
if 3 in TByteSet(byte1) then 
...

// bzw. direkt die Variable "byte1" als diesen Typ definieren, ohne ständige Konvertierung

Gerade bei Bitmasken arbeite ich gern Hexadezimal, anstatt Dezimal. (binäre Zahlen kann Delphi leider nicht)
$01 = 1
$02 = 2
$04 = 4
$08 = 8
$10 = 16
$20 = 32
$40 = 64
$80 = 128