Javascript - how to quickly construct a binary representation for an array of distinct positive integers

Question

I am currently working on a Javascript project where I need to quickly generate a unique group_ID for a non-empty array of distinct positive integers, such as:

var a = [1, 2, 5]

In this case, I would like to identify this array using a binary number: 0b11001 (i.e., a binary number says that elements 1, 2 and 5 are in the group and the other elements are absent). Here, the ordering doesn't matter so I would get the same group_ID === 0b11001 for [2, 1, 5] or [5, 1, 2].

I am wondering if there is a quick way to generate this ID using either native JS, or underscore/lodash?

Stefan Haustein · Accepted Answer · 2016-04-12 00:37:12Z

4

The trick is to shift 1 to the left by the element to get the corresponding binary number for each element. Then use bitwise "or" to collect them:

var groupId = 0;
for (var i = 0; i < a.length; i++) {
   groupId |= 1 << (a[i] - 1);
}

Or a bit more "modern" as a one-liner:

groupId = a.reduce(function(p, c) {return p | (1 << (c - 1));}, 0);

Note that this will only work for numbers up to 32 in JavaScript. For bigger numbers, you'll need to use an array for the group ids (perhaps hidden in a BitSet class)

p.s. For numbers > 32 (and including 0):

var groupId = [];
for (var i = 0; i < a.length; i++) {
  var e = a[i];
  groupId[Math.floor(e / 32)] |= 1 << (e % 32);
}
// convert the array to a hex string or similar for simpler handling

edited Apr 12, 2016 at 0:37

answered Apr 11, 2016 at 23:51

Stefan Haustein

18.9k3 gold badges40 silver badges54 bronze badges

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

3 Comments

CupawnTae Over a year ago

even more moderner a.reduce((p, c) => p | 1 << (c - 1), 0);

Berk U. Over a year ago

Thank you! It's unfortunate that there isn't an easy way to make it work for numbers greater than 32. The solution that I came up with is: groupId = _.reduce(a, function(bin, s){return bin + Math.pow(2,s-1)}, 0).toString(2) though this outputs a String. Out of curiosity, will JS be faster when working with binary numbers vs Strings?

Stefan Haustein Over a year ago

Yes binary numbers are faster and your solution needs a check for duplicates (if they may occur) and it's still limited to 53

Collectives™ on Stack Overflow

Javascript - how to quickly construct a binary representation for an array of distinct positive integers

1 Answer 1

3 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

3 Comments

Your Answer

Sign up or log in

Post as a guest

Related