DoubleDabble in Java
Ich wollte als Fingerübung wieder einmal einen Algorithmus umsetzen - dieses Mal doubledabble zum Encoding und Decoding von packed binary-coded decimal (BCD) Zahlen. Ich stellte zu meinem Erstaunen fest, dass das nicht einfach ist...
Der Algorithmus erfordert ein Bitfeld variabler - aber fester - Länge, die nicht notwendigerweise ein Vielfaches von 8 ist.
Ich suchte lange, fand aber keine Datenstruktur (Datentyp, Klasse - der Name ist egal), die diese Anforderungen erfüllte. Die Klasse BitSet ist leider genau das: ein Set, das keine Größenbeschränkung aufweist.
Mit den Klassen Long und Byte ist einem hier auch nicht geholfen, da diese die Einschränkung jhaben, dass die Anzahl der Bits hierin (oder in Arrays daraus) immer ein Vielfaches von 8 sind. Auch BigInteger ist keine Hilfe - Auch dieser Typ hat keine Beschränkung seiner Größe - er wächst bei Bedarf einfach mit...
Hmmm - habe ich hier wirklich eine Facette gefunden, die noch ungelöst ist? Und sollte man eine Klasse (einen Typ) implementieren, der das gewünschte Verhalten abbildet?
Tests sollten einfach sein: Die Klasse leitet man von Number ab und schreibt zunächst jede Menge Tests, die alle arithmetischen Funktionen in den ebenfalls davon abgeleiteten Ordinaltypen mit entsprechenden Sonderfällen prüfen und sicherstellen, dass das Verhalten der neuen Klasse mit den jeweils passenden Bitlängen identisch ist. Anschließend gilt es noch entsprechende Tests für Bitlängen, die keine Vielfachen von 8 sind zu schreiben und deren Korrektheit zu validieren.
Ich habe mich letztlich dagegen entschieden, diesen Aufwand zu betreiben - statt dessen habe ich eine Klasse geschrieben, die die 5 gewünschten Operationen
- shl - Shift Left,
- shr - Shift Right,
- sshl - Signed Shift Left
- rol - Rotate Left
- ror - Rotate Right
Letztlich habe ich mich dazu entschieden, statt dessen ein BitSet zu nutzen und eine Maske dazuzubauen, die aus n Einsen besteht (wobei 'n' die Länge des BitSet sein soll) - dann muss nur noch nach jeder Operation das Ergebnis der Operation logisch UND-verknüpft werden mit dieser Maske. Die Maske kann gebaut werden indem man die Methode set benutzt.
Auch diese Idee wurde letztlich verworfen und ich habe mich entschieden, einfach nach jeder Operation die Methode get zu nutzen, um das Bitset wieder auf die ursprüngliche Länge zu stutzen.
Der eigentliche Grund, von der Idee der Nutzung der eingebauten Typen abzuweichen war die zusätzliche Schwierigkeit, dass das Ergebnis der Methode toByteArray der Klasse BigInteger genau anders herum zählt als das BitSet: Man kann einen BigInteger und ein BitSet nicht einfach über deren jeweilige Byte-Array Representation ineinander umwandeln: Der Wert 65531 ergibt als Byte-Array aus BigInteger heraus eines, dessen 0-tes Byte den Wert 0 und dessen zweites den Wert -1 hat - die Methode toString eines daraus erzeugten BitSet allerdings liefert als Indices {8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 19, 20, 21, 22, 23} und nicht das (von mir) erwartete Resultat {0, 1, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15}.
Der aktuelle Stand der Implementation zeigt eine Konvertierungsmethode:
public class FixedLengthBitSet extends java.lang.Object implements java.lang.Cloneable
{
private final int length;
private java.util.BitSet value;
private boolean carry;
public FixedLengthBitSet(int length)
{
this((java.util.BitSet)null,length);
}
public FixedLengthBitSet(java.lang.Number n,int length)
{
this(java.math.BigInteger.valueOf(n.longValue()),length);
}
public FixedLengthBitSet(java.math.BigInteger bi,int length)
{
this(valueOf(bi,length),length);
}
public FixedLengthBitSet(java.util.BitSet bs,int length)
{
super();
if(length<1)
throw new java.lang.IllegalArgumentException("length must be at least 1!");
this.length=length;
this.value=bs!=null?(java.util.BitSet)bs.clone():new java.util.BitSet();
}
@Override
public Object clone() throws CloneNotSupportedException
{
FixedLengthBitSet clone=(FixedLengthBitSet)super.clone();
clone.value=(java.util.BitSet)value.clone();
return clone;
}
private void clearCarry()
{
carry=false;
}
private void carryLeft()
{
carry=value.get(length-1);
}
private void carryRight()
{
carry=value.get(0);
}
public FixedLengthBitSet ror()
{
clearCarry();
boolean sign=value.get(0);
carryRight();
shr();
if(sign)
value.set(length-1);
return this;
}
public FixedLengthBitSet rol()
{
clearCarry();
boolean sign=value.get(length-1);
carryLeft();
shl();
if(sign)
value.set(0);
return this;
}
public FixedLengthBitSet shr()
{
clearCarry();
carryRight();
value=value.get(1,length);
return this;
}
public FixedLengthBitSet sshr()
{
clearCarry();
boolean sign=value.get(length-1);
carryRight();
shr();
if(sign)
value.set(length-1);
return this;
}
public FixedLengthBitSet shl()
{
return shl(false);
}
public FixedLengthBitSet shl(boolean carry)
{
clearCarry();
java.util.BitSet bs=new java.util.BitSet();
carryLeft();
for(int i=1,j=0;i<length;++i,++j)
{
if(value.get(j))
bs.set(i);
else
bs.clear(i);
}
if(carry==true)
bs.set(0);
value=bs;
return this;
}
private static java.util.BitSet valueOf(java.math.BigInteger bi, int length)
{
java.util.BitSet bs=valueOf(bi);
if(bi.signum()==-1)
{
for(int i=length-1;i>=0;--i)
{
if(bs.get(i)==false)
bs.set(i);
else
break;
}
}
return bs;
}
public static java.util.BitSet valueOf(java.math.BigInteger bi)
{
byte[] bytes=bi.toByteArray();
byte[] reverted=new byte[bytes.length];
for(int i=bytes.length-1;i>=0;--i)
{
reverted[i]=bytes[bytes.length-1-i];
}
java.util.BitSet bs=java.util.BitSet.valueOf(reverted);
return bs;
}
public java.math.BigInteger asTwosComplementBigInteger()
{
java.math.BigInteger rv=java.math.BigInteger.valueOf(0);
for(int i=0;i<length-1;++i)
{
if(value.get(i))
rv=rv.add(java.math.BigInteger.valueOf(1<<i));
}
if(value.get(length-1))
rv=rv.subtract(java.math.BigInteger.valueOf(1<<(length-1)));
return rv;
}
public java.math.BigInteger asBigInteger()
{
java.math.BigInteger rv=java.math.BigInteger.valueOf(0);
for(int i=length-1;i>=0;--i)
{
rv=rv.shiftLeft(1);
if(value.get(i))
rv=rv.or(java.math.BigInteger.valueOf(1));
}
return rv;
}
public int getLength()
{
return length;
}
public java.util.BitSet getValue()
{
return value.get(0,length);
}
public boolean isCarry()
{
return carry;
}
@Override
public java.lang.String toString()
{
return asBigInteger().toString()+" -- "+asTwosComplementBigInteger().toString()+" --" +asBigInteger().toString(16)+" -- "+getValue().toString();
}
}
Und damit lässt sich dann auch der Algorithmus umsetzen:
private static java.util.List<de.elbosso.util.lang.FixedLengthBitSet> doubleDabble(int in)
{
java.math.BigInteger input=java.math.BigInteger.valueOf(in);
int n=input.bitLength();
de.elbosso.util.lang.FixedLengthBitSet original=new de.elbosso.util.lang.FixedLengthBitSet(input,n);
java.util.List<de.elbosso.util.lang.FixedLengthBitSet> nibbles=new java.util.LinkedList<>();
nibbles.add(new de.elbosso.util.lang.FixedLengthBitSet(4));
for(int i=0;i<n;++i)
{
original.shl();
boolean bitSet=original.isCarry();
for(int j=0;j<nibbles.size();++j)
{
if(nibbles.get(j).asBigInteger().intValue()>4)
{
nibbles.set(j,new de.elbosso.util.lang.FixedLengthBitSet(nibbles.get(j).asBigInteger().add(java.math.BigInteger.valueOf(3)),4));
}
nibbles.get(j).shl(bitSet);
bitSet=nibbles.get(j).isCarry();
}
if(bitSet==true)
{
nibbles.add(new de.elbosso.util.lang.FixedLengthBitSet(java.math.BigInteger.valueOf(1),4));
}
}
return nibbles;
}
Vor 5 Jahren hier im Blog
-
Schachtel und Deckel 2
07.09.2021
Und wieder eine Schachtel - diesmal in verschiedenen Größen und mit verschiedenen Deckeln - ohne Schere, ohne Leim...
Weiterlesen
Tags
AI und ML Android Basteln C und C++ Chaos Datenbanken Docker dWb+ ESP Wifi Garten Geo Go GUI Hardware Java Jupyter JupyterBinder Komponenten Links Linux Markdown Markup Music Numerik OpenSource PKI-X.509-CA Präsentationen Python QBrowser Rants Raspi Revisited Security Software-Test sQLshell TeleGrafana Verschiedenes Video Virtualisierung Windows Upcoming...
Neueste Artikel
-
LinkCollections 2026 IX
Nach der letzten losen Zusammenstellung (für mich) interessanter Links aus den Tiefen des Internet von 2026 folgt hier gleich die nächste:
Weiterlesen -
Neue Projektidee fürs Homelab
Ich habe ja bereits mehrere Artikel geschrieben, in denen ich darüber berichtete, wie ich - vor allem wegen des Preises - die Raspis in meinem Haushalt gegen sehr preisgünstige gebrauchte Thin-Clients mit Intel- und AMD-Prozessoren ersetzte.
Weiterlesen -
sQLshell, WASM und SQLite
Ich habe in letzter Zeit häufiger mal über die Unterstützung von SQLite in der sQLshell berichtet - unter anderem über die Möglichkeiten, Extensions zu nutzen...
Weiterlesen
Manche nennen es Blog, manche Web-Seite - ich schreibe hier hin und wieder über meine Erlebnisse, Rückschläge und Erleuchtungen bei meinen Hobbies.
Wer daran teilhaben und eventuell sogar davon profitieren möchte, muss damit leben, daß ich hin und wieder kleine Ausflüge in Bereiche mache, die nichts mit IT, Administration oder Softwareentwicklung zu tun haben.
Ich wünsche allen Lesern viel Spaß und hin und wieder einen kleinen AHA!-Effekt...
PS: Meine öffentlichen Codeberg-Repositories findet man hier.