JS - bitwise 1st set bit

Uczymy się rozpoznawać pozycję pierwszego „ustawionego” bitu, czyli pierwszy bit o wartości 1. Do dzieła!

Najpierw zobaczmy czym jest pozycja i waga oraz liczba binarna (raczej przypomnijmy sobie):

Pozycje              3     2      1      0
Wagi:              ( 8 ) ( 4 )  ( 2 )  ( 1 )
Liczba (8):          1     0      0      0
Baza: 2
Wartość:           1*2^3   -      -      -

Tak działają liczby binarne. Pozycje liczymy od 0 od prawej, wagi to baza^pozycja, wartość to cyfra * waga (dotyczy to wszystkich pozycyjnych systemów liczbowych z dowolną bazą, sprawdźmy dziesiętny sobie).

Ok, wypiszmy sobie wagi od pozycji 0 do 4 czyli od 1 do 16:

let num = 1;

while(num <= 16){
    console.log(num);
    num = num << 1;
}

// 1
// 2
// 4
// 8
// 16

Nie jest to trudne – wystarczy zacząć od liczby 1 i przesuwać bitowo o 1. Przykład:

Pozycje              3     2      1      0
Wagi:              ( 8 ) ( 4 )  ( 2 )  ( 1 )
Liczba (1):          0     0      0      1
Liczba << 1:         0     0      1      0
Liczba << 1:         0     1      0      0
Liczba << 1:         1     0      0      0

Ok, a jak sprawdzić, czy dany bit jest włączony? Sprawdźmy, czy 8 ma bit 8 włączony:

console.log(8 & 8); //8
console.log(8 & 1); //0

console.log(9 & 8); //8
console.log(9 & 1); //1

8 ma włączony bit 8 (& maska 8 różne od 0) i wyłączony bit 1. 9 ma zarówno włączone bity i 8 i 1 (& maska różna od 0).

W ramach ćwiczenia proponuję to sobie rozpisać z kartką papieru. Ja natomiast przedstawiam już naszą funkcję:

function positionOfFirstSetBit(num, max=15){

    let mask = 1;
    let pos = 0;
    //position is zero-indexed counted from right
    while(pos !== max){
        if((num & mask) !== 0){
            return pos;
        }
        pos++;
        mask = mask << 1;
    }
    return -1;

}

console.log(positionOfFirstSetBit(8));
//3
console.log(positionOfFirstSetBit(9));
//0

Ok, zobaczmy:

Pozycje              3     2      1      0
Wagi:              ( 8 ) ( 4 )  ( 2 )  ( 1 )
Liczba (8):          1     0      0      0
Liczba (9):          1     0      0      1

Więcej bitowych już niedługo.

JS – bitwise 1st set bit