Get all "power of 2" numbers contained in input number

JavaScript performance comparison

Test case created by MalcolmFeth

Preparation code


      
      <script>
Benchmark.prototype.setup = function() {
  /* SUMMARY
  Real life example based on filters. I have a filtering functionality where each number (power of 2) is assigned specific filter options, for example: 1=address, 2=photos, 4=reviews, 8=email, 16=chat, 32=somethingElse... etc
  
  I want to pass to a function a number which will return me an array of all filters applied (order of the array doesn't matter). We don't want to assign name to any number at this stage yet.
  - It has to be fast, doesn't have to be pretty.
  - Doesn't have to support more than 32 bits
  
  A couple of examples:
  getNumbers(12);
  // Array [ 8, 4 ]
  
  getNumbers(17);
  // Array [ 16, 1 ]
  
  getNumbers(1234)
  // Array [ 1024, 128, 64, 16, 2 ]
  
  getNumbers(23456)
  // Array [ 16384, 4096, 2048, 512, 256, 128, 32 ]
  
  The below examples were written by different people, who iterate through their code to make it faster. # next to a name means another attempt. You can see how approaches are different and how to solve such a problem. */
  
  
  
  function andrew1(value) {
      var returnNumbers = [];
  
      var highestValue = 1;
      for (i = 1; i <= value; i=i*2) { 
          highestValue = i;
      }
  
      for (i = highestValue; i >= 1; i=i/2) { 
          if (value >= i) {
              if(value - i >= 0) {
                  returnNumbers.push(i);
              }
  
              value = value - i;
          }
      }
  
      return returnNumbers;
  }
  
  
  function andrew2(value) {
      
          var returnArray = [];
      
          // find the highest power number
          var highestValue = Math.pow( 2, Math.floor( Math.log(value) / Math.log(2) ) );
    
          while (value > 0) {
    
            if (value >= highestValue) {
              returnArray.push(highestValue);
              value-=highestValue;
            }
    
            highestValue/=2;
          }
      
          return returnArray;
      }
  
  
  
  
  function jake1(num) {
      return num.toString(2).split('').reverse().reduce((acc, value, idx) => {
          if(value == 1) acc.push(Math.pow(2, idx));
          return acc;
      }, []);
  }
  
  
  function jake2(num) {
     let r = [];
     for (let i = 1; i <= num; i = i * 2) {
         if (i & num) r.push(i);
     }
     return r;
  }
  
  
  
  function theo1(n){
      return (n).toString(2).split('').reverse().map((v,i)=>v==="1" && Math.pow(2,i)).filter(Boolean);
  }
  
  
  function theo3(n){
      let bit = 1;
      if(n>Number.MAX_SAFE_INTEGER){
          throw new Error('Maximum int of 9007199254740992 exceeded')
      }
      let bits=[];
      while(bit<=Number.MAX_SAFE_INTEGER){
          if(bitwiseAnd(n,bit)){
              bits.push(bit);
          }
          bit*=2;
      }
      return bits;
  }
  // for theo's function
  function bitwiseAnd(v1, v2) {
      var hi = 0x80000000;
      var low = 0x7fffffff;
      var hi1 = ~~(v1 / hi);
      var hi2 = ~~(v2 / hi);
      var low1 = v1 & low;
      var low2 = v2 & low;
      var h = hi1 & hi2;
      var l = low1 & low2;
      return h*hi + l;
  }
  
  
  function theo4(n){
      let bit = 1;
      let bits=[];
      //if 32 bit int
      if(n<=2147483647){
          for(;bit<=n;bit*=2){
              if(n & bit){
                  bits.push(bit);
              }
          }
          return bits;
      }
      //if 64 bit int
      for(;bit<=n;bit*=2){
          if(bitwiseAnd(n,bit)){
              bits.push(bit);
          }
      }
      return bits;
  }
  
  
  // too slow to run
  function callum1 (number) {
      if (number === 0) return [];
      let removed = 0;
      while (Math.log2(number) % 1 !== 0) {
          number--;
          removed++;
      }
      const fn = callum1;
      const result = fn(removed);
      return [number, ...result];
  }
  
  // too slow to run
  function callum2 (number) {
      const result = [];
      while (number > 0) {
          let removed = 0;
          while (Math.log2(number) % 1 !== 0) {
              number--;
              removed++;
          }
          result.push(number);
          number = removed;
      }
      return result;
  }
  
  function callum3 (number) {
      const result = [];
      while (number > 0) {
          let remainder = Math.floor(Math.log2(number));
          let bit = Math.pow(2, remainder);
          result.push(bit);
          number = number - bit;
      }
      return result;
  }
  
  
  function stanz1(n) {
    const result = [];
    let i = 1;
    while (i <= n) {
      const val = n & i;
      if (val) {
          result.push(val);
          n -= val;
      }
      i *= 2;
    }
    return result;
  }
  
  function stanz2(n) {
  	const r = [];
  	let i = n;
  	for (let j = 1; j <= n; j *= 2) {
  		if (i & 1) r.push(j);
  		i >>= 1;
  	}
  	return r;
  }
  
  
  function ashley1(n){
   let r = [], d = 1;
   n = n.toString(2);
   for ( var x=n.length-1;x>=0;x--){
      let c = n.charAt(x);
      if ( c == "1" ){
          r.push(d);
     }
      d = d*2;
   }
   return r;
  }
  
  
  function joe1 (num) {
      
      const bin = num.toString(2)
      const len = bin.length - 1
      
      const res = []
      let cur = 1
      
      for (let i = len; i >= 0; i--) {
      
          if(bin[i] === '1') {
              res.push(cur)
          }
          
          cur = cur << 1
      }
      
      return res
  }
  
  
  function mariusz1(value){
    let remainder = value;
    
    const permissions = [];
  
    while (remainder > 0) {
      let counter = 1;
  
      while (counter < remainder + 1) {
        counter *= 2;
      }
      const max = counter === 1 ? counter : counter / 2;
  
      permissions.push(max);
  
      remainder -= max;
    }
  
    return permissions;
  };

};
</script>

Test runner

Warning! For accurate results, please disable Firebug before running the tests. (Why?)

Java applet disabled.

Testing in CCBot 2.0.0 / Other 0.0.0
Test Ops/sec
Andrew 1
andrew1(4);
andrew1(15);
andrew1(1234567);
andrew1(1073741823);
andrew1(1073741824);
pending…
Andrew 2
andrew2(4);
andrew2(15);
andrew2(1234567);
andrew2(1073741823);
andrew2(1073741824);
pending…
Jake 1
jake2(4);
jake2(15);
jake2(1234567);
jake2(1073741823);
jake2(1073741824);
pending…
Jake 2
jake2(4);
jake2(15);
jake2(1234567);
jake2(1073741823);
jake2(1073741824);
pending…
Theo 1
theo1(4);
theo1(15);
theo1(1234567);
theo1(1073741823);
theo1(1073741824);
pending…
Theo 3
theo3(4);
theo3(15);
theo3(1234567);
theo3(1073741823);
theo3(1073741824);
pending…
Callum 3
callum3(4);
callum3(15);
callum3(1234567);
callum3(1073741823);
callum3(1073741824);
pending…
Stanz 1
stanz1(4);
stanz1(15);
stanz1(1234567);
stanz1(1073741823);
stanz1(1073741824);
pending…
Stanz 2
stanz2(4);
stanz2(15);
stanz2(1234567);
stanz2(1073741823);
stanz2(1073741824);
pending…
Ashley 1
ashley1(4);
ashley1(15);
ashley1(1234567);
ashley1(1073741823);
ashley1(1073741824);
pending…
Joe 1
joe1(4);
joe1(15);
joe1(1234567);
joe1(1073741823);
joe1(1073741824);
pending…
Mariusz 1
mariusz1(4);
mariusz1(15);
mariusz1(1234567);
mariusz1(1073741823);
mariusz1(1073741824);
pending…

Compare results of other browsers

Revisions

You can edit these tests or add even more tests to this page by appending /edit to the URL.

0 Comments