Elegant Bits entfernen

Narses · Verfasst: Sa 16.01.10 15:01

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:

markieren

Delphi-Quelltext

1:	procedure DeleteBit(var Value: Cardinal; const Bit: Byte);

Ich mach mal ein Beispiel, wie ich mir das vorstelle:

markieren

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

_________________
There are 10 types of people - those who understand binary and those who don´t.

FinnO · Verfasst: Sa 16.01.10 15:14

markieren

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 · Verfasst: Sa 16.01.10 15:20

Moin!

Vielen Dank für den Vorschlag.

FinnO hat folgendes geschrieben :

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

Narses hat folgendes geschrieben :

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

cu
Narses

_________________
There are 10 types of people - those who understand binary and those who don´t.

FinnO · Verfasst: 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 · Beiträge: 762 Erhaltene Danke: 127

Jetzt nur mal auf die Schnelle:

1. Maske alles Einsen links vom Löschbit (vorher in Array)
2. Maske alles Einsen rechts vom Löschbit (vorher in Array)
((Original AND 1. Maske) SHR 1) OR (Original AND 2. Maske)

ub60

jfheins · Beiträge: 918 Erhaltene Danke: 158 Win 10 VS 2013, VS2015

Mein Ansatz:

markieren

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 · Beiträge: 208 Erhaltene Danke: 2

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!

markieren

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:

markieren

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 · Beiträge: 762 Erhaltene Danke: 127

Sirke hat folgendes geschrieben :

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:

ub60

BenBE · Verfasst: Sa 16.01.10 20:30

markieren

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 icon

Narses 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 Narses: Beiträge zusammengefasst---

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

markieren

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;

_________________

Anyone who is capable of being elected president should on no account be allowed to do the job.
Ich code EdgeMonkey - In dubio pro Setting.

	Mitgliederliste
	Gruppen
	Das Team
	Richtlinien
	Synonyme