Javascript Bitwise Op

Question

I was wondering if there's a way to find out if given binary pattern, two or more of the 1's are within another binary pattern. I say pattern because the actual value of it does not determine if one is within another.

For example,

0001 1110 0000 0000
0001 1111 0000 0000
--> true

0001 0000 1100 0000
0001 1111 0000 0000
--> false

0001 1100 0000 1000
0001 0000 0000 1111
--> true

0001 1000 1100 0000
0001 0000 0000 1111
--> false

I tried using variety of AND/OR/XOR/NOT but not sure how to do it. Please help!

So the question about the data in question is like this:

const RANKS = [
  0b0000000001110001,
  0b0000001001000110,
  0b0001001100000100,
  0b0000000011011000,
];

I'm trying to loop over RANKS to see if it matches a pattern:

const PATTERNS = [
  0b0001111100000000,
  0b0000111110000000,
  0b0000011111000000,
];

Only 2 of the 1's from RANK has to "fit" in PATTERN to consider as true

Does each array contain four elements? Can you include array representation of data at stacksnippets? — guest271314, Sep 06 '16 at 06:45
The second one is false because only 1 of the 1's fits the pattern to match — cocacrave, Sep 06 '16 at 06:46
You can use `&` and then [count bits](http://stackoverflow.com/q/109023/1048572) — Bergi, Sep 06 '16 at 06:56

score 4 · Answer 1 · edited May 23 '17 at 10:29

4

If you and the two patterns together, you will get a pattern with bits set only in the positions where both patterns have a 1. You can then use one of the algorithms for Hamming Weight to count the number of bits that are set. The simplest algorithm would be the following function count:

function count(num) {
  var c = 0;
  while (num > 0) {
    if (num & 1) {
      c++;
    }
    num = num >>> 1;
  }
  return c;
}
console.log(count(1)); /* 1 */
console.log(count(2)); /* 1 */
console.log(count(3)); /* 2 */

H/T to here for the term Hamming Weight.

edited May 23 '17 at 10:29

Community

1
1

answered Sep 06 '16 at 06:54

andyg0808

1,367
8
18

Thanks for providing another solution. This works as well. – cocacrave Sep 06 '16 at 07:05

Amadan · Accepted Answer · 2016-09-06T07:37:50.607

function sharesAtLeastTwoBits(x, y) {
  var a = x & y;
  if (!a) return false;
  while (!(a & 1)) a >>>= 1;
  return a != 1;
}

console.log(sharesAtLeastTwoBits(
  0b0001111000000000,
  0b0001111100000000
))

console.log(sharesAtLeastTwoBits(
  0b0001000011000000,
  0b0001111100000000
))

console.log(sharesAtLeastTwoBits(
  0b0001110000001000,
  0b0001000000001111
))

console.log(sharesAtLeastTwoBits(
  0b0001100011000000,
  0b0001000000001111
))

Use & to figure out which bits they have in common. If no bits are in common, false. If not, shift right till the lowest bit is at 0th position; if it is the only bit that is 1, the whole number is 1, so false again; otherwise true.

EDIT: andyg0808's answer is more general.

I tried your solution and it works perfectly. Thanks you so much. — cocacrave, Sep 06 '16 at 07:01

Javascript Bitwise Op

2 Answers2