CODEWITHSUNDEEP
javascriptbit-manipulationbitwise-operatorsbit
cocacrave
cocacrave

Reputation: 2633

Javascript Bitwise Op

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

Upvotes: 4

Views: 144

Answers (2)

Amadan
Amadan

Reputation: 198526

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.

Upvotes: 2

andyg0808
andyg0808

Reputation: 1403

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.

Upvotes: 4

Related Questions