How to add bits in JavaScript

Question

Say you have two integers 10 and 20. That is 00001010 and 00010100. I would then like to just basically concat these as strings, but have the result be a new integer.

00001010 + 00010100 == 0000101000010100

That final number is 2580.

However, I am looking for a way to do this without actually converting them to string. Looking for something more efficient that just does some bit twiddling on the integers themselves. I'm not too familiar with that, but I imagine it would be along the lines of:

var a = 00001010 // == 10
var b = 00010100 // == 20
var c = a << b //   == 2580

Note, I would like for this to work with any sequences of bits. So even:

var a = 010101
var b = 01110
var c = a + b == 01010101110

a + (b << 8) is likely what you are looking for, or use typed arrays — ASDFGerte
– ASDFGerte, Commented Aug 25, 2018 at 20:39

score 2 · Accepted Answer · 2018-08-25 22:26:22Z

2

You basic equation is:

c = b + (a << 8).

The trick here is that you need to always shift by 8. But since a and b do not always use all 8 bits in the byte, JavaScript will automatically omit any leading zeros. We need to recover the number of leading zeros (of b), or trailing zeros of a, and prepend them back before adding. This way, all the bits stay in their proper position. This requires an equation like this:

c = b + (a << s + r)

Where s is the highest set bit (going from right to left) in b, and r is the remaining number of bits such that s + r = 8.

Essentially, all you are doing is shifting the first operand a over by 8 bits, to effectively add trailing zeros to a or equally speaking, padding leading zeros to the second operand b. Then you add normally. This can be accomplishing using logarithms, and shifting, and bitwise OR operation to provide an O(1) solution for some arbitrary positive integers a and b where the number of bits in a and b do not exceed some positive integer n. In the case of a byte, n = 8.

// Bitwise log base 2 in O(1) time
function log2(n) {

  // Check if n > 0

  let bits = 0;

  if (n > 0xffff) {
      n >>= 16;
      bits = 0x10;
  }

  if (n > 0xff) {
      n >>= 8;
      bits |= 0x8;
  }

  if (n > 0xf) {
      n >>= 4;
      bits |= 0x4;
  }

  if (n > 0x3) {
      n >>= 2;
      bits |= 0x2;
  }

  if (n > 0x1) {
      bits |= 0x1;
  }

  return bits;
}

// Computes the max set bit
// counting from the right to left starting
// at 0. For 20 (10100) we get bit # 4.
function msb(n) {

  n |= n >> 1;
  n |= n >> 2;
  n |= n >> 4;
  n |= n >> 8;
  n |= n >> 16;

  n = n + 1;

  // We take the log here because
  // n would otherwise be the largest
  // magnitude of base 2. So, for 20,
  // n+1 would be 16. Which, to 
  // find the number of bits to shift, we must 
  // take the log base 2
  return log2(n >> 1);
}

// Operands
let a = 0b00001010  // 10
let b = 0b00010100  // 20

// Max number of bits in
// in binary number
let n = 8

// Max set bit is the 16 bit, which is in position
// 4. We will need to pad 4 more zeros
let s = msb(b) 

// How many zeros to pad on the left
// 8 - 4 = 4
let r = Math.abs(n - s)

// Shift a over by the computed 
// number of bits including padded zeros
let c = b + (a << s + r)

console.log(c)

Output:

Notes:

This is NOT commutative.
Add error checking to log2() for negative numbers, and other edge cases.

References:

edited Aug 25, 2018 at 22:26

answered Aug 25, 2018 at 21:22

user5063151

Sign up to request clarification or add additional context in comments.

2 Comments

GottZ Over a year ago

i like how your references have nothing to do with javascript. this is all you need to explain it: developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/…

user5063151 Over a year ago

@GottZ They are code references that provide intuition as to how I came up with a potential language agnostic solution the original post, which I find more valuable than a specification on JavaScript bitwise operations. I think the original poster understands bitwise operation / arithmetic. The roadblock is USING it to come up with an efficient solution to a particular problem. Also, the link you posted uses parseInt() to convert a String object to binary. The requirement of the original post says he strictly would like to avoid using strings. Thank you for your concern though!

user3463521 · Accepted Answer · 2018-08-29 18:40:20Z

so the problem:
a is 10 (in binary 0000 1010)
b is 20 (in binary 0100 0100)
you want to get 2580 using bit shift somehow.

if you right shift a by 8 using a<<=8 (this is the same as multiplying a by 2^8) you get
1010 0000 0000 which is the same as 10*2^8 = 2560.
since the lower bits of a are all 0's (when you use << it fills the new bits with 0) you can just add b on top of it 1010 0000 0000 + 0100 0100 gives you 1010 0001 0100.

so in 1 line of code, it's var result = a<<8 + b.

Remember in programming languages, most of them have no explicit built-in types for "binary". But everything is binary in its nature. so int is a "binary", an object is "binary" ....etc. When you want to do some binary operations on some data you can just use the datatype you have as operands for binary operations.

this is a more general version of how to concatenate two numbers' binary representations using no string operations and data

/*
  
  This function concate b to the end of a and put 0's in between them.  
  
  b will be treated starting with it's first 1 as its most significant bit
  
  b needs to be bigger than 0, otherwise, Math.log2 will give -Infinity for 0 and NaN for negative b
  
  padding is the number of 0's to add at the end of a
*/

function concate_bits(a, b, padding) {

  //add the padding 0's to a
  a <<= padding;

  //this gets the largest power of 2
  var power_of_2 = Math.floor(Math.log2(b));
  var power_of_2_value;

  while (power_of_2 >= 0) {
    power_of_2_value = 2 ** power_of_2;
    a <<= 1;
    if (b >= power_of_2_value) {
      a += 1;
      b -= power_of_2_value;
    }
    power_of_2--;
  }
  return a;
}

//this will print 2580 as the result
let result = concate_bits(10, 20, 3);
console.log(result);

james · Accepted Answer · 2018-08-25 22:29:46Z

0

Note, I would like for this to work with any sequences of bits. So even:

var a = 010101
var b = 01110
var c = a + b == 01010101110

This isn't going to be possible unless you convert to a string or otherwise store the number of bits in each number. 10101 010101 0010101 etc are all the same number (21), and once this is converted to a number, there is no way to tell how many leading zeroes the number originally had.

answered Aug 25, 2018 at 22:29

james

13.4k9 gold badges50 silver badges74 bronze badges

Collectives™ on Stack Overflow

How to add bits in JavaScript

3 Answers 3

2 Comments

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

2 Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related