# 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…

## Revisions

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