Trjtdtk

Let's say I have a max 32-bit integer -

const a =
 ((2 ** 32) - 1)
 
const b =
 parseInt("11111111111111111111111111111111", 2) // 32 bits, each is a one!
 
console.log(a === b) // true

console.log(a.toString(2))
// 11111111111111111111111111111111 (32 ones)

console.log(b.toString(2))
// 11111111111111111111111111111111 (32 ones)

So far so good. But now let's say I want to make a 32-bit number using eight (8) 4-bit numbers. The idea is simple: shift (<<) each 4-bit sequence into position and add (+) them together -

const make = ([ bit, ...more ], e = 0) =>
 bit === undefined
 ? 0
 : (bit << e) + make (more, e + 4)

const print = n =>
 console.log(n.toString(2))

// 4 bits
print(make([ 15 ])) // 1111

// 8 bits
print(make([ 15, 15 ])) // 11111111

// 12 bits
print(make([ 15, 15, 15 ])) // 111111111111

// 16 bits
print(make([ 15, 15, 15, 15 ])) // 1111111111111111

// 20 bits
print(make([ 15, 15, 15, 15, 15 ])) // 11111111111111111111

// 24 bits
print(make([ 15, 15, 15, 15, 15, 15 ])) // 111111111111111111111111

// 28 bits
print(make([ 15, 15, 15, 15, 15, 15, 15 ])) // 1111111111111111111111111111

// almost there ... now 32 bits
print(make([ 15, 15, 15, 15, 15, 15, 15, 15 ])) // -1 :(

I'm getting -1 but the expected result is 32-bits of all ones, or 11111111111111111111111111111111.

Worse, if I start with the expected outcome and work my way backwards, I get the expected result -

const c =
 `11111111111111111111111111111111`

const d = 
 parseInt(c, 2)
 
console.log(d) // 4294967295

console.log(d.toString(2) === c) // true

I tried debugging my make function to ensure there wasn't an obvious problem -

const make = ([ bit, ...more ], e = 0) =>
 bit === undefined
 ? `0`
 : `($bit << $e) + ` + make (more, e + 4)

console.log(make([ 15, 15, 15, 15, 15, 15, 15, 15 ])) 
// (15 << 0) + (15 << 4) + (15 << 8) + (15 << 12) + (15 << 16) + (15 << 20) + (15 << 24) + (15 << 28) + 0

The formula looks like it checks out. I thought maybe it was something to do with + and switched to bitwise or (|) which should effectively do the same thing here -

const a =
 parseInt("1111",2)
 
const b =
 (a << 0) | (a << 4)
 
console.log(b.toString(2)) // 11111111

const c =
 b | (a << 8)
 
console.log(c.toString(2)) // 111111111111

However, I get the same bug with my make function when attempting to combine all eight (8) numbers -

const make = ([ bit, ...more ], e = 0) =>
 bit === undefined
 ? 0
 : (bit << e) | make (more, e + 4)

const print = n =>
 console.log(n.toString(2))


print(make([ 15, 15, 15, 15, 15, 15, 15 ])) // 1111111111111111111111111111 (28 bits)

print(make([ 15, 15, 15, 15, 15, 15, 15, 15 ])) // -1 :(

What gives?

The goal is to convert eight (8) 4-bit integers into a single 32-bit integer using JavaScript - this is just my attempt. I'm curious where my function is breaking, but I'm open to alternative solutions.

I'd like to avoid converting each 4-bit integer to a binary string, mashing the binary strings together, then parsing the binary string into a single int. A numeric solution is preferred.

The bitwise operators will result in a signed 32 bit number, meaning that if the bit at position 31 (counting from the least significant bit at the right, which is bit 0) is 1, the number will be negative.

To avoid this from happening, use other operators than << or |, which both result in a signed 32-bit number. For instance:

(bit * 2**e) + make (more, e + 4)

Forcing unsigned 32-bit

Bit shifting operators are designed to force the result into the signed 32-bit range, at least that is claimed on mdn (at the time of writing):

The operands of all bitwise operators are converted to signed 32-bit integers

This is in fact not entirely true. The >>> operator is an exception to this. EcmaScript 2015, section 12.5.8.1 states that the operands are mapped to unsigned 32 bit before shifting in the 0 bits. So even if you would shift zero bits, you'd see that effect.

You would only have to apply it once to the final value, like for instance in your print function:

console.log((n>>>0).toString(2))

BigInt solution

If you need even more than 32 bits, and your JavaScript engine supports BigInt like some already do, then use BigInts for the operands involved in the bitwise operators -- these will then not use the 32-bit signed number wrapping (notice the n suffixes):

const make = ([ bit, ...more ], e = 0n) =>
 bit === undefined
 ? 0n
 : (bit << e) + make (more, e + 4n)

const print = n =>
 console.log(n.toString(2))

// Test
for (let i=1; i<20; i++) 
 print(make(Array(i).fill(15n))) // longer and longer array...

NB: If you get an error running the above, try again with Chrome...