Spielereien mit bit wise Operatoren und langen Binärzahlen

berndoa

Top Contributor
Hallo,
ich habe die folgende Teilaufgabe die ich unzählige Male lösen muss:
Es seien 2 Zahlen A und B gegeben in Binärform mit 49 bits Länge (von denen 6 bits 1 sind der Rest Null).
1. Was für einen Datentyp kann ich für die nehmen?
Weil normales int könnte für zahlen, die im worstcase 2^49-1 groß sind, unpassend sein.
Und will eigentlich kein Big Integer benutzen oder so, weil für mich nur wirklich wichtig ist,
welche 6 der 49 bits 1 sind.

Was das, wenn man es als eine Dezimalzahl "umdeutet" genau für einen Wert hätte, ist für mich unwichtig.
Das mit den 49 bit ist einfach nur eine passende Darstellungsart zur Codierung beim vorliegenden Problem.


Nun müsste ich rausfinden ob die 2 Zahlen in >=3 Stellen übereinstimmen.
Hier wäre ein bit wises Und sichelrich sinnvoll (deswegen überhaupt auch die Darstellung)
um (in binär ausgedrückt) die Anzahl an gemeinsamen Stellen zu finden.

Nun ist es in der Aufgabe so dass ich
eine Zahl A habe und eine Liste an Zahl L.
und nun im Endefekt gucken will ob sich in der Liste L mindestens eine Zahl finden lässt,
die >=3 stellen gemeinsam hat.

Ich habe das gefühl, mit klug gewählten bitoperationen und Co. könnte man das durchaus klug umsetzen.

Und Effizienz wäre wichtig da ich wirklich seeeeehr viele Zahlen kreuz und quer vergleichen muss :)

Hat Jemand eine gute Idee wie ich das sinnvoll umsetzen kann?
 

httpdigest

Top Contributor
Naja, wenn du 49 Bits brauchst und int offensichtlich nur 32 Bits speichern kann, würde sich das 64-bittige long anbieten.
Für den Test auf "wieviele Bits haben zwei Zahlen gemeinsam" bietet sich, wie du schon sagtest, ein bitweises UND an, zusammen mit der Operation, die als "Population Count" bekannt ist und in Java in der Long Klasse als bitCount() implementiert ist.
Unter x86 wird dabei dann die Instruktion POPCNT verwendet.
 

berndoa

Top Contributor
kann man irgendwie bei einer zahl, ohne jetzt was Eigenes zu schreiben, irgendwie rausfinden welche (6) bits ungleich null ist, gibts da vorgefertigte Funktionen dazu? :)
 

httpdigest

Top Contributor
kann man irgendwie bei einer zahl, ohne jetzt was Eigenes zu schreiben, irgendwie rausfinden welche (6) bits ungleich null ist, gibts da vorgefertigte Funktionen dazu? :)
Keine eine Operation, nein.
Was soll denn da auch als Ergebnis rauskommen? Die 6 Bits, die ungleich null sind, sind dann halt die sechs bits in der Zahl selbst. Also -> die Zahl selbst.
Aber du willst vermutlich die Positionen bzw. Indizes der 6 Bits als Zahlen haben.

Aber du kannst dir was zusammenbauen mit logischen Rechts-Shifts (>>>) und Long.numberOfTrailingZeros().
Oder umgekehrt mit logischen Links-Shifts (<<) und Long.numberOfLeadingZeros().
 
Ähnliche Java Themen
  Titel Forum Antworten Datum
Developer_X Java String Spielereien Java Basics - Anfänger-Themen 18
K Für was braucht man die left und right shift operatoren? Was bringen die, also welchen Zweck haben die? Java Basics - Anfänger-Themen 15
Kleinerals2 NaN Operatoren Java Basics - Anfänger-Themen 3
S Und-Abfrage mit mehreren Ungleich-Operatoren Java Basics - Anfänger-Themen 17
P Datentypen, Klassen, Operatoren, Wrapperklassen Java Basics - Anfänger-Themen 2
D Erste Schritte Operatoren zur Manipulation von Bits "~" Java Basics - Anfänger-Themen 5
M Operatoren Umwandlung div. Operatoren Java Basics - Anfänger-Themen 7
V Operatoren Was will mir die Tabelle in meinem Lehrbuch sagen? (logische Operatoren) Java Basics - Anfänger-Themen 4
S Bitweise Operatoren" >>>",">>","<<" erklärung Java Basics - Anfänger-Themen 5
G operatoren Java Basics - Anfänger-Themen 3
beatles Operatoren Operatoren - Berechnung Java Basics - Anfänger-Themen 40
T Verständnisfrage Zuweisungs-/arithmet. Operatoren Java Basics - Anfänger-Themen 2
X Shift-Operatoren Java Basics - Anfänger-Themen 1
P Bitweise Operatoren Java Basics - Anfänger-Themen 2
Phillip Bitweise Operatoren Java Basics - Anfänger-Themen 11
C Operatoren Java Basics - Anfänger-Themen 6
P Taschenrechner, operatoren Java Basics - Anfänger-Themen 4
M Einfache und Doppelte Operatoren Java Basics - Anfänger-Themen 3
S Operatoren & Terminierung Java Basics - Anfänger-Themen 1
A Bitweise Operatoren Java Basics - Anfänger-Themen 1
O Priorität bei Operatoren Java Basics - Anfänger-Themen 4
N Potenzierung durch einfache Operatoren Java Basics - Anfänger-Themen 13
B Geschwindigkeitsabhängigkeit von Anz. d. Operatoren pro Zeile Java Basics - Anfänger-Themen 12
M hexadezimal in binär mit Hilfe von Shift-Operatoren Java Basics - Anfänger-Themen 6
S Arithmetische Operatoren Java Basics - Anfänger-Themen 7
L Erste Schritte Fragen zu Arrays, Inkrement Operatoren, Dekrement Operatoren ? Java Basics - Anfänger-Themen 9
lulas[]args Fehler - Logische Operatoren Java Basics - Anfänger-Themen 9
H Nur Zahlen, Klammern und Operatoren Java Basics - Anfänger-Themen 3
D Frage zu Bit Operatoren in der Programmierung Java Basics - Anfänger-Themen 9
P Anzahl der else if Operatoren begrenzt?? Java Basics - Anfänger-Themen 7
L [Logische Operatoren] referenzierbar? Java Basics - Anfänger-Themen 3
W Was tun die Operatoren ? und : (Bedingungen) Java Basics - Anfänger-Themen 15
W Datentypen Operatoren für eigenen Datentyp nutzen Java Basics - Anfänger-Themen 2
G Logische und Bitweise Operatoren Java Basics - Anfänger-Themen 2
S Datentypen Operatoren und Ausdrücke (formel richtig rechnen) Java Basics - Anfänger-Themen 8
E Logische Operatoren && und & Java Basics - Anfänger-Themen 14
? Operatoren && || Java Basics - Anfänger-Themen 10
M Aufgabe Arithmetische Operatoren Java Basics - Anfänger-Themen 12
H While Schleife mit Operatoren Java Basics - Anfänger-Themen 14
T Rechnen mit Operatoren Java Basics - Anfänger-Themen 2
M Arithmetische Operatoren Java Basics - Anfänger-Themen 40
V Sonderzeichen als eigene "Operatoren" im JTextField Java Basics - Anfänger-Themen 4
M Sind ternäre Operatoren für einen guten Programmierstil wichtig ? Java Basics - Anfänger-Themen 10
E IF Anweisung mit logischen Operatoren Java Basics - Anfänger-Themen 18
JStickman Was bringen Bit-Operatoren? Java Basics - Anfänger-Themen 14
J Matheaufgabe aus String mit mehreren Operatoren Java Basics - Anfänger-Themen 16
D Logische Operatoren Java Basics - Anfänger-Themen 6
D Grundlagen - Operatoren Java Basics - Anfänger-Themen 5
1 Datentypen Rückgabetyp von Java-Operatoren Java Basics - Anfänger-Themen 2
V Bitweise Operatoren in der Grafikprogrammierung Java Basics - Anfänger-Themen 2
SebSnake Operatoren für eigene Datentypen Java Basics - Anfänger-Themen 3
M logische operatoren Java Basics - Anfänger-Themen 2
C Variablen für Operatoren Java Basics - Anfänger-Themen 3
W Rangfolge von Operatoren Java Basics - Anfänger-Themen 16
N zahlen und operatoren gemischt in einem Feld Java Basics - Anfänger-Themen 9
T Logische Operatoren Java Basics - Anfänger-Themen 39
C Dynamische Operatoren! Java Basics - Anfänger-Themen 5
G Shift Operatoren Java Basics - Anfänger-Themen 4
R Bedingte Opeatoren / Verschachtelte Operatoren Java Basics - Anfänger-Themen 4
7 Operatoren in der While Schleife Java Basics - Anfänger-Themen 5
H Postfix Operatoren Java Basics - Anfänger-Themen 2
S Variablen + Operatoren "mixen" Java Basics - Anfänger-Themen 5
F Experimente mit Bit-Operatoren Java Basics - Anfänger-Themen 7
G Nutzen von bitweisen Operatoren Java Basics - Anfänger-Themen 8
J Operatoren in Java Java Basics - Anfänger-Themen 2
S Verwendung bitweiser Operatoren Java Basics - Anfänger-Themen 6
R Binäre logische Operatoren Java Basics - Anfänger-Themen 21

Ähnliche Java Themen

Neue Themen


Oben