Function to generate an Int from a series of bits

Question

I wrote the following function in order to handle some data from a QR code:

func genInt(fromBitArray array: [Int]) -> Int {
    var n = 0
    for i in 0...array.count - 1 {
        n += array[i] << ((array.count - 1) - i)
    }
    return n
}

genInt(fromBitArray: [1, 1, 0]) would return 6.

Is there a better/more efficient way to do this?

Answer 1

Improving the code

Your code computes $$ a_0 2^{n-1} + a_1 2^{n-2} + \ldots a_{n-2} 2 + a_{n-1} \, , $$ that is the polynomial $$ P(x) = a_0 x^{n-1} + a_1 x^{n-2} + \ldots a_{n-2} x + a_{n-1} \, $$ evaluated at \$ x=2 \$. A well-known, efficient method to evaluate polynomials is Horner's method: $$ P(x) = (\ldots ((a_0 x + a_1) x + a_2) x + \ldots ) x + a_0 \, . $$

Applied to your task that gives

func genInt(fromBitArray array: [Int]) -> Int {
    var n = 0
    for i in 0...array.count - 1 {
        n = 2 * n + array[i]
    }
    return n
}

Instead of the bit shift (by a variable amount) we have now multiplications by the fixed factor \$ 2 \$. But this can be simplified further. Inside the loop we need now only the array element at the current index, but not the index itself. Therefore we can enumerate the array instead:

func genInt(fromBitArray array: [Int]) -> Int {
    var n = 0
    for digit in array {
        n = 2 * n + digit
    }
    return n
}

And for this kind of combining array (or more general: sequence) elements there is a dedicated method in the Swift standard library, reduce():

func genInt(fromBitArray array: [Int]) -> Int {
    return array.reduce(0) { (accum, digit) in
        return 2 * accum + digit
    }
}

Naming

The “official” Swift naming conventions are describe in the API Design Guidelines, e.g.

• Name variables, parameters, and associated types according to their roles, rather than their type constraints.
• Begin names of factory methods with “make”, e.g. x.makeIterator().
• Avoid abbreviations.

With these rules in mind I would suggest something like

func makeInteger(fromBits array: [Int]) -> Int

Or if one sees this as a way to construct an integer then a custom initializer would be appropriate

extension Int {
    init(bits array: [Int]) {
        self = array.reduce(0) { (accum, digit) in
            return 2 * accum + digit
        }
    }
}

// Example:
let value = Int(bits: [1, 1, 0])

Miscellaneous

It is expected that the array contains only the values zero and one. With an assertion this can be verified during the test phase, without performance impact on the released code:

extension Int {
    init(bits array: [Int]) {
        self = array.reduce(0) { (accum, digit) in
            assert(digit == 0 || digit == 1, "invalid binary digit")
            return 2 * accum + digit
        }
    }
}

If you want to create other integer types from a bit array in the same manner then you can defined the initializer on the BinaryInteger protocol instead:

extension BinaryInteger {
    init(bits array: [Int]) {
        self = array.reduce(0) { (accum, digit) in
            assert(digit == 0 || digit == 1, "invalid binary digit")
            return 2 * accum + Self(digit)
        }
    }
}

// Example:
let value = Int16(bits: [1, 1, 0])