JS - clz32 (nasze własne)

Poprzednio nauczyliśmy się liczyć trailing 0s w liczbach dwójkowych, teraz odtworzymy funkcjonalność znaną z Math.clz32. Do dzieła.

Zastanówmy się, jaka jest największa wartość jednego 1 w int32:

let pow1 = Math.pow(2, 31);
console.log(pow1); //2147483648

To nie jest największa liczba. To tylko liczba, która z przodu ma jedynkę. Jeszcze ma 31 miejsc, gdzie może być jedynka lub 0. Zobaczmy to i owo:

let pow1 = Math.pow(2, 31);
console.log(pow1); //2147483648
console.log(Math.clz32(pow1)); //0
console.log(Math.clz32(pow1+1)); //0 
console.log(Math.clz32(pow1+100)); //0
console.log(Math.clz32(pow1+1000)); //0

Czasami warto sobie pewne rzeczy zwizualizować. Zobaczmy w Pythonie:

print(1 << 31) #2147483648
print("{0:b}".format(1 << 31))
#10000000000000000000000000000000

print("{0:b}".format(8))
#1000

print("{0:b}".format(8 << 4))
#10000000

print("{0:b}".format(8 << 8))
#100000000000

print("{0:b}".format(8 << 20))
#100000000000000000000000

print((1 << 31) & (1 << 30)) #0
print((1 << 31) & (1 << 31)) #2147483648

Jeszcze jeden rzut oka, który może nas naprowadzić na rozwiązanie:

console.log((1 << 31) & (1 << 31)); //-2147483648
console.log((1 << 31) & (1 << 30)); //0
console.log((1 << 31) & (1 << 29)); //0
console.log((1 << 31) & (1 << 28)); //0
console.log((1 << 31) & (1 << 27)); //0
console.log((1 << 31) & (1 << 26)); //0
console.log((1 << 31) & (1 << 25)); //0

Ok, nasza funkcja:

function countLeadingZeros(num)
{
    
    let total_bits = 32;
    let zeros = 0;

    while ((num & (1 << (total_bits - 1))) === 0)
    {
        num = (num << 1);
        zeros++;
    }
  
    return zeros;
}

Nasze testy:

console.log(countLeadingZeros(1 << 31)); //0
console.log(countLeadingZeros(1 << 30)); //1
console.log(countLeadingZeros(1 << 29)); //2
console.log(countLeadingZeros(1 << 28)); //3
console.log(countLeadingZeros(1 << 27)); //4
console.log(countLeadingZeros(1 << 26)); //5
console.log(countLeadingZeros(1 << 25)); //6

console.log(Math.clz32(8), countLeadingZeros(8)); //28 28
console.log(Math.clz32(9), countLeadingZeros(9)); //28 28
console.log(Math.clz32(32), countLeadingZeros(32)); //26 26
console.log(Math.clz32(34), countLeadingZeros(34)); //26 26

Jak to działa? Weźmy 8 i 9 dla przykładu i naszą maskę, która jest niezmienna (2^31 albo 1 << 31):

print("{0:b}".format(1 << 31))
#10000000000000000000000000000000
print("{0:b}".format(8))
#1000
print("{0:b}".format(9))
#1001

Jest maska i jest liczba. Dopiszmy sobie zera samemu:

Maska - 10000000000000000000000000000000
8     - 00000000000000000000000000001000
9     - 00000000000000000000000000001001

No i teraz robimy & tak długo jak & daje 0. I nic z maska nie robimy, tylko liczbę przesuwamy o << 1 w lewo. I ilość takich przesunięć zliczamy. Bardzo proste, ale trzeba to sobie rozpisać, rozrysować, przerobić.

JS – clz32 (nasze własne)