CODEWITHSUNDEEP
arraysgobit-manipulationbitshift
Kasay Mardis
Kasay Mardis

Reputation: 33

Bitwise bit shifting and why this solution works

I've been doing code fights on codefights.com and I came upon this problem below. I have figured out the problem on my own, but when i researched other peoples solutions I found one that was much shorter than mine, but I cant seem to understand why they did what they did.

The question goes:

You are given an array of up to four non-negative integers, each less than 256. Your task is to pack these integers into one number M in the following way:

The first element of the array occupies the first 8 bits of M; The second element occupies next 8 bits, and so on. Return the obtained integer M.

Note: the phrase "first bits of M" refers to the least significant bits of M - the right-most bits of an integer. For further clarification see the following example.

Example

For a = [24, 85, 0], the output should be arrayPacking(a) = 21784.

An array [24, 85, 0] looks like [00011000, 01010101, 00000000] in binary. After packing these into one number we get 00000000 01010101 00011000 (spaces are placed for convenience), which equals to 21784.

Their answer was:

func arrayPacking(a []int) (sum int) {
    for i := range a {
        sum += a[len(a) - i - 1] << uint((len(a) - i - 1) * 8)
    }
    return
}

How is this code returning the right amount of shift just by using 0, 8, 16, etc. intervals? I've been researching bitwise a lot lately, but I still can't seem to reason why this works.

Upvotes: 0

Views: 2757

Answers (2)

ReyCharles
ReyCharles

Reputation: 1792

the bitshifting by multiples of 8 is the same as muliplying by multiples of 256, e.g. x << 0*8 == x * 256⁰, x << 1*8 == x * 256¹, x << 2*8 == x * 256² etc., so the code can be rewritten like this, using math.Pow:

func arrayPacking(a []int) (sum int) {
  for i := range a {
    sum += a[len(a) - i - 1] * int(math.Pow(256, (len(a) - i - 1)))
  }
  return
}

Or is your question why this sort of packing works?

Upvotes: 1

peterSO
peterSO

Reputation: 166578

First, write the solution in Go. We convert little-endian, base-256 digits to a base-2 (binary) number. Shifting left by 8 bits multiplies by 256.

package main

import (
    "fmt"
)

func pack(digits []int) (number int) {
    // digits are little-endian, base-256 (1 << 8 = 256)
    for i, digit := range digits {
        number += digit << uint(i*8)
    }
    return number
}

func main() {
    a := []int{24, 85, 0}
    m := pack(a)
    fmt.Println(m)
}

Playground: https://play.golang.org/p/oo_n7CiAHwG

Output:

21784

Now you should be able to figure out their ugly looking answer:

func arrayPacking(a []int) (sum int) {
    for i := range a {
        sum += a[len(a) - i - 1] << uint((len(a) - i - 1) * 8)
    }
    return
}

Upvotes: 1

Related Questions