CODEWITHSUNDEEP
javascriptdata-structuresbit-manipulation
Ravi Sevta
Ravi Sevta

Reputation: 3085

How could I count bit from large number in javascript?

I have a large number stored in string.

let txt = '10000000000000041';

So how could I count bit presenting in it's a binary format. for example, the binary format of 9 is 1001, and no of 1's is 2.

What I did so far:

const countOne = (num) => {
  let c = 0;
  while (num > 0) {
    num &= num - 1;
    c++;
  }
  return c;
}

console.log(countOne(+'9'));
console.log(countOne(+'10000000000000041'));

This code is working fine, but not for large value, because Number in JavaScript cannot hold such large value, so it's giving the wrong answer.

I found similar questions but not for large value.

Upvotes: 2

Views: 282

Answers (2)

Mister Jojo
Mister Jojo

Reputation: 22320

For those who do not have the BigInt, here is a solution to convert to binary via an Euclidean division:

let txt ='10000000000000041'
,   bin = GetBinary(txt)
;
console.log('Base 10 = ', txt )
console.log('Base 2  = ', bin )
console.log('number of digits on 1 = ', bin.replace(/0/g,'').length )

function GetBinary(strNum)
{
  let Bin = ''
  ,   val = strNum
  ,   Rep = null
  ;
  for(let l=0;l<200;l++)  // loop limitation to 200 by security
  {
    Rep = Div_2(val)
    val = Rep.R
    Bin = Rep.D + Bin
    if (val==='') break;
  } 
  if (val!=='') console.log( 'too much loops for conversion')
  return Bin
}

function Div_2(sNum)
{
  let D = R = ''                 // dividande, results
  ,   d = x = r = 0             // temp vals
  ;
  for(let p=0;p<sNum.length;p++)
  {
    D += sNum.charAt(p)
    d = parseInt(D,10)
    if ( d < 2 ) R += '0'
    else
    {
      x = Math.trunc(d / 2)
      r = d % 2
      D = r.toString(10)
      R += x.toString(10)
    }
  }
  R = R.replace(/\b0+/g, '')     // remove leading zeros
  D = parseInt(D,10).toString() // .except the last one
  return { R, D }
}

[edit= minor errors corrected + info]

info : The number max of useful loops (in GetBinary()), is equal to
Math.ceil(Math.log2(Math.pow(10,n)))
where n is the number of digits in base 10.
The 'explanations' are here:
Is there a formula for calculating or estimating the number of digits of a binary integer?

(thanks to Jaromanda X)

Upvotes: 1

CertainPerformance
CertainPerformance

Reputation: 370759

In newer engines (Chrome, FF, Opera, and Node at least, see compatibility table), just cast to a BigInt first:

let txt='10000000000000041';
const countOne = (num) => {
  let c = 0;
  while (num > 0) {
    num &= num - 1n;
    c++;
  }
  return c;
}
console.log(countOne(BigInt(txt)));
console.log(countOne(BigInt(1)));
console.log(countOne(BigInt(2)));
console.log(countOne(BigInt(3)));
console.log(countOne(BigInt(4)));
console.log(countOne(BigInt(5)));
console.log(countOne(BigInt(6)));
console.log(countOne(BigInt(7)));
<script>
try {
  eval('1n');
} catch(e) {
  throw "Your browser doesn't support BigInt syntax yet";
}
</script>

10000000000000041 in binary is 100011100001101111001001101111110000010000000000101001, so 23 is correct:

console.log(
  [...'100011100001101111001001101111110000010000000000101001']
  .reduce((a, b) => a + (b === '1'), 0)
);

Upvotes: 3

Related Questions