JS - single 1 in binary

Piszemy funkcję, która sprawdzi, czy podana liczba posiada tylko jedną „jedynkę” w swojej reprezentacji binarnej. Do dzieła.

Ok, przypomnę poprzednią lekcję:

function countTrailingZeros(num){

    let cnt = 0;
    let flag= 1;

    
    while((num & flag) === 0){
        cnt++;
        flag = flag << 1;
    }

    return cnt;
}

console.log(countTrailingZeros(8)); //3
console.log(countTrailingZeros(9)); //0
console.log(countTrailingZeros(1)); //0
console.log(countTrailingZeros(16)); //4
console.log(countTrailingZeros(6)); //1

Tu mamy zera po prawej wyliczane. A zera po lewej? W Int32?

Proszę:

console.log(Math.clz32(8));// 28
console.log(countTrailingZeros(8)); //3

Jak nietrudno się domyślić, liczba zawierająca tylko jedną jedynkę będzie miała liczbę zer w int32 równą 31. Mamy patent na zera po prawej i po lewej?

Mamy. Niewiele więcej potrzebujemy:

function singleOneInBinary_bad(number){
      
    function countTrailingZeros(num){

        let cnt = 0;
        let flag= 1;
    
        
        while((num & flag) === 0){
            cnt++;
            flag = flag << 1;
        }
    
        return cnt;
    }

    return (countTrailingZeros(number) + Math.clz32(number)) === 31;
}


console.log(singleOneInBinary_bad(8)); //true
console.log(singleOneInBinary_bad(4)); //true
console.log(singleOneInBinary_bad(2)); //true
console.log(singleOneInBinary_bad(1)); //true
console.log(singleOneInBinary_bad(9)); //false
console.log(singleOneInBinary_bad(6)); //false

Ok, a da się inaczej? Zobaczmy na coś takiego:

function valuesInBinary_v2(num){
    return Array.from({length: num}, (_, i) => {
        return 1 * Math.pow(2, num-1-i);
    });
}

console.log(valuesInBinary_v2(8));
//[ 128, 64, 32, 16, 8, 4, 2, 1 ]

To są wartości dla cyfr binarnych robiliśmy już to. Pobawmy się tym:

for(const val of valuesInBinary_v2(8)) {
    console.log(val, Math.log2(val));
}
// 128 7 
// 64 6 
// 32 5 
// 16 4 
// 8 3 
// 4 2 
// 2 1 
// 1 0

Jak widać każda daje normalny logarytm. Pomajstrujmy przy tym:

for(const val of valuesInBinary_v2(8)) {
    console.log(val-1, Math.log2(val-1));
}

// 127 6.9886846867721655 
// 63 5.977279923499917 
// 31 4.954196310386875 
// 15 3.9068905956085187 
// 7 2.807354922057604 
// 3 1.584962500721156 
// 1 0 
// 0 -Infinity

Teraz już powinniśmy rozumieć, że liczba z jednym 1 w binarnym będzie miała którąś z potęg 2 jako wartość. To jest ta liczba daje normalny logartym 2.

Czyli nasze sprawdzenie wygląda tak:

function singleOneInBinary(num){
    return Number.isInteger(Math.log2(num));
}

console.log(singleOneInBinary(8)); //true
console.log(singleOneInBinary(4)); //true
console.log(singleOneInBinary(2)); //true
console.log(singleOneInBinary(1)); //true
console.log(singleOneInBinary(9)); //false
console.log(singleOneInBinary(6)); //false

O logarytmach było w poprzednich lekcjach.

JS – single 1 in binary