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