Oppgave 1

1. n + (n << 1)
2. n + (n << 2)
3. (n << 1) + (n << 2)
4. (n << 3) - n
5. (n << 6) + (n << 4) + (n << 2)

Oppgave 2

Divisor d	n / d  kan erstattes med	Intervall for n
11	n * 47663 >>> 19	0 <= n < 90112
12	(n >> 2) * 43691 >>> 17	0 <= n < 393216
13	n * 20165 >>> 18	0 <= n < 212992
14	(n >> 1) * 74899 >>> 19	0 <= n < 114688

Oppgave 3

Her vil tidsforbruket være avhengig av prosessor, operativsystem og Java-kompilator. Bruk av en Pentium 4 - 2,8GHz, Windows XP og Java v. 1.5.0_06 gav et tidsforbruk på ca. 1 sekund for N = 360000000.

1. Her ble faktisk tidsforbruket litt mindre, dvs. ca 0,9 sekunder.
2. Ca. 1 sekund. Det har altså ingen hensikt å erstatte multiplikasjonen med bitforskyvninger.
3. Begge bruker ca. 1 sekund.
4. Divisjon med 10 bruker ca. 6 ganger så lang tid som multiplikasjon med 10.
5. n / 5 bruker 5 - 6 ganger så lang tid som n * 52429 >>> 18 .
6. n / 10 bruker 5 - 6 ganger så lang tid som (n >> 1) * 52429 >>> 18 .
7. Bruker ca. halvparten så lang tid som n / 5 .
8. Bruker ca. like lang tid som n / 5 .

Oppgave 4

  public static int div5(int n)
  {
    int q = (n >> 3) + (n >> 4);
    q += (q >> 4);
    q += (q >> 8);

    int r = n - q*5;

    return q + (r*52429 >>> 18);
  }

Oppgave 5

Flg. kode er hentet fra en fil under avsnittet "More on Division by Constants" på www.hackersdelight.org:

  public static int div3(int n)
  {
    int q = (n >> 2) + (n >> 4);
    q += (q >> 4);
    q += (q >> 8);
    q += (q >> 16);
    int r = n - q*3;
    return q + (11*r >> 5);
  }

  public static int div7(int n)
  {
    int q = (n >> 1) + (n >> 4);
    q += (q >> 6);
    q += (q >> 12) + (q >> 24);
    q >>= 2;
    int r = n - q*7;
    return q + ((r + 1) >> 3);
  }

Oppgave 6

  public static String toString(int n)
  {
    if (n == -2147483648) return "-2147483648";

    boolean negativ = false;
    if (n < 0)
    {
      n = -n;
      negativ = true;
    }

    char[] c = new char[11];  // maks 10 siffer + fortegn
    int i = 11, m = 0;

    if (n >= 100000)
    {
      m = n / 100000;
      n = n - m * 100000;
    }

    for (;;)
    {
      int q = (n >> 1) * 52429 >>> 18;
      c[--i] = (char)(n - q*10 + 48);
      n = q;
      if (n == 0)
      {
        if (m > 0) {n = m; m = 0;}
        else break;
      }
    }
    if (negativ) c[--i] = '-';

    return new String(c,i,11-i);
  }