Random.nextInt(int)

[Franz Degenhardt]

Hallo!

nextInt(int) ist in java 1.4.2 folgendermassen implementiert:

    public int nextInt(int n) {
        if (n<=0)
            throw new IllegalArgumentException("n must be positive");

        if ((n & -n) == n)  // i.e., n is a power of 2
            return (int)((n * (long)next(31)) >> 31);

        int bits, val;
        do {
            bits = next(31);
            val = bits % n;
        } while(bits - val + (n-1) < 0);
        return val;
    }

Irdendwie kamen mir da Zweifel am Sinn der Implentierung. Ist der Ausdruck
(n & -n) == n nicht immer wahr für positive n?
Und wenn ja, wieso ist die Methode danach nicht zuende. Hat dafür jemand eine Erklärung?

Grüsse TrueSun

 

[Thomas Darimont]

Hallo!

(n & -n) == n

ist wahr für alle Potenzen von 2, wie's da steht ... im Bereich 0 ... Integer.MAX_VALUE

Gruß Tom

 

[Franz Degenhardt]

Hmm

Ich kann mich noch dunkel erinnern, dass minus durch eine 1 im Vorzeichenbit dargestellt wird.
5 wäre also binär:
0 ...00101
-5 binär:
1...00101

a b a&b
1 1 1
1 0 0
0 1 0
0 0 0

dann ist (5 & -5) = 5 damit wäre die Bedingung erfüllt, obwohl 5 keine Potenz von 2 ist.

Wo ist mein Fehler?

 

[Thomas Darimont]

Hallo!

Nicht ganz:

 5 -> 101
-5 -> 11111111111111111111111111111011

Gruß Tom

 

[Franz Degenhardt]

Hi!

*schäm* Hast recht, wo hab ich nur diese komische Regel für negative Zahlen her? *sig*
Ich musste dann direkt mal googeln, wer mal ausführlicher lesen will: http://www.sap-img.com/java/java-binary-representation-of-integers.htm

Danke auf jeden Fall
Grüsse TrueSun

 

[Thomas Darimont]

Hallo!

Das ganze nennt sich 2-er Komplement.

Gruß Tom