Entwickler-Ecke

Algorithmen, Optimierung und Assembler - Elegant Bits entfernen


Narses - Sa 16.01.10 15:01
Titel: Elegant Bits entfernen
Moin!

Aufgabe: ein Bit aus einer Binärzahl löschen (analog zu Delete() für Strings, nur eben auf Bitbasis).

Auch hier wieder, grundsätzlich kriegt man das schon hin, aber wie macht man es "elegant"? ;)

Um die Aufgabe etwas konkreter zu gestalten (*aus letztem Thread gelernt hat* :)), hier ein Header:

Delphi-Quelltext 
1:
 
procedure DeleteBit(var Value: Cardinal; const Bit: Byte);
Ich mach mal ein Beispiel, wie ich mir das vorstelle:

Quelltext 
1:
2:
3:
 
vorher:  10010101
löschen: Bit 3
nachher: 01001101
Die Bits nach dem Delinquenten sollen also "von Links" nachrücken, auffüllen mit 0. :idea:

Ich bin auf eure Vorschläge gespannt. :zustimm:

cu
Narses


FinnO - Sa 16.01.10 15:14

Delphi-Quelltext 
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
 
procedure SwapBits(var Value: Cardinal; const BitX, BitY: Byte); //nach BenBE
begin
    Value := Value XOR ( ((1 shl BitX) OR (1 shl BitY)) * ( ((Value shr BitX) XOR (Value shr BitY)) AND 1 ) ) ;
end;

procedure DeleteBit(var Value: Cardinal; const Bit : Byte);
var
  i: Integer;
begin
  for i := Bit downto 1 do
  begin
    SwapBits(Value,i, i-1);
  end;
  Value := Value shr 1;
end;


Vorgehen:

das Zielbit ganz nach rechts durchschieben und dann einmal nach rechts shiften.


Narses - Sa 16.01.10 15:20
Moin!

Vielen Dank für den Vorschlag. ;)

user profile iconFinnO hat folgendes geschrieben Zum zitierten Posting springen:
Vorgehen: das Zielbit ganz nach rechts durchschieben und dann einmal nach rechts shiften.
user profile iconNarses hat folgendes geschrieben Zum zitierten Posting springen:
Auch hier wieder, grundsätzlich kriegt man das schon hin, aber wie macht man es "elegant"? :zwinker:
cu
Narses


FinnO - Sa 16.01.10 15:21
=P ich hab keinerlei anspruch auf Eleganz^^. Ich würde sagen, es wäre schonmal deutlich eleganter, n Bits im Block verschieben zu können. Dann müsste man nur einmal tauschen und einmal shiften.


ub60 - Sa 16.01.10 15:35
Jetzt nur mal auf die Schnelle:

ub60


jfheins - Sa 16.01.10 15:37
Mein Ansatz:

Delphi-Quelltext 
1:
2:
3:
4:
5:
6:
7:
8:
9:
 
procedure DeleteBit(var Value: Cardinal; const Bit: Byte)
var
  Mask, right: Cardinal;
begin
Mask := (1 shl Bit) - 1;
right := Value and Mask;
Value := Value shr 1;
Value := (Value and not Mask) or right;
end;


Sirke - Sa 16.01.10 15:38
Ich würde sagen eine einfache Lösung ist es den vorderen Block zu maskieren und dann den hinteren Block um 1 zu verschieben und ebenfalls zu maskieren!


Delphi-Quelltext 
1:
2:
3:
4:
5:
6:
7:
 
procedure DeleteBit(var Value: Cardinal; const Bit : Byte);
var
  mask: Cardinal;
begin
  mask := (1 shl Bit) - 1;
  Value := ( Value and mask ) or ( ( Value shr 1 ) and ( not mask ) );
end;


Ich bin mir gerade nicht mehr genau sicher, ob die Bitoperationen so korrekt sind, gerade bei dem Befehl not mask, ob dieser wirklich die negativ Maske über den gesamten Cardinal ist!

Das ganze sollte ja in etwa das machen:

Quelltext 
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
 
Value    = 10110100100111011101 ;  Bit = 7
1 << Bit = 00000000000010000000
mask     = 00000000000001111111

Value    = 10110100100111011101
mask     = 00000000000001111111
-------------------------------
     AND = 00000000000001011101 => t1

Value    = 10110100100111011101
   SHR 1 = 01011010010011101110
NOT mask = 11111111111110000000
-------------------------------
     AND = 01011010010010000000 => t2

t1       = 00000000000001011101
t2       = 01011010010010000000
-------------------------------
      OR = 01011010010011011101


€dit sagt: Schon wieder bin ich der langsamste... :( ... ABER mit der elegantesten Lösung! =)


ub60 - Sa 16.01.10 16:38
user profile iconSirke hat folgendes geschrieben Zum zitierten Posting springen:
Schon wieder bin ich der langsamste... :( ... ABER mit der elegantesten Lösung! =)

Eigentlich war das GENAU die Lösung, die ich beschrieben hatte :roll:
Aber meinetwegen, Deine ist eleganter :lol: :lol:

ub60


BenBE - Sa 16.01.10 20:30

Delphi-Quelltext 
1:
 
Result := ((Value and not (1 shl Bit)) + Value and ((1 shl Bit)-1)) shr 1;


Obwohl, ich glaub, ich erklär's für user profile iconNarses heut mal:

Das zu löschende Bit auf Null setzen, alle Bits rechts davon auf die Zahl drauf addieren und das Ergebnis insgesamt ein Bit nach Rechts schieben ...

---Moderiert von user profile iconNarses: Beiträge zusammengefasst---

Ach ja, als kleine Ergänzung für mehrere Bits anhand einer Maske:


Delphi-Quelltext 
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
 
procedure DeleteBitsEx(var Value: Cardinal; Mask: Cardinal);
var
    TMask: Cardinal;
    BC: Byte;
begin
    BC := 0;
    While Mask <> 0 do
    Begin 
        //Count bits ...
        Inc(BC);

        //Make obvious we can reuse partial/intermediate results here ...
        //C: TMask ^= Mask = (TMask = Mask) & (Mask-1);
        TMask := Mask;
        Mask := Mask and (Mask - 1);
        TMask := Mask xor TMask;

        //Remove the current selected Bit from Value ...
        Value := (Value and not TMask) + Value and (TMask - 1);
    end;

    //Move the zeros to the left ... (Actually also a ROR would do)
    Value := Value shr BC;
end;


Entwickler-Ecke.de based on phpBB
Copyright 2002 - 2011 by Tino Teuber, Copyright 2011 - 2024 by Christian Stelzmann Alle Rechte vorbehalten.
Alle Beiträge stammen von dritten Personen und dürfen geltendes Recht nicht verletzen.
Entwickler-Ecke und die zugehörigen Webseiten distanzieren sich ausdrücklich von Fremdinhalten jeglicher Art!