Oppgave 1

Som bitkoder: 1 1 0 2 2 3 1 3. Som posisjoner: 9 17 32 10 6 11 33 7.

Oppgave 2

Som bitkoder: 1 1 0 2 3 2 1 3. Som posisjoner: 9 17 32 6 7 10 33 11.

Oppgave 3

Som bitkoder: 2 3 0 4 3 1 2 5 3 1. Som posisjoner: 10 11 32 12 7 17 18 13 19 33.

Oppgave 4

  public static int[] finnBitkoderHøyre(int[] lengder)
  {
    // tar som gitt at ingen lengde er større enn 31
    int[] a = new int[32];  // antall tegn av hver lengde

    for (int lengde : lengder) a[lengde]++;  // teller opp

    int[] p = new int[32];  // posisjonen til første bladnode
    p[31] = 0x7fffffff;     // 0111.....1111

    for (int k = 31; k > 0; k--) p[k - 1] = (p[k] - a[k])/2;

    int[] bitkoder = new int[lengder.length];

    for (int i = bitkoder.length - 1; i >= 0; i--)
      if (lengder[i] > 0) bitkoder[i] = p[lengder[i]]--;

    return bitkoder;
  }