Piszemy funkcję, która sprawdza ilość zer po prawej stronie liczby, to jest od prawego końca do pierwszej jedynki bądź końca. Zaczynamy.
Ok, pomyślmy jak możemy sprawdzić rekurencyjnie ile zer ma liczba 8:
1 0 0 0
0 0 0 1 &
--------
0 0 0 0 <-- 0 znaczy kontynuuj
1 0 0 0
0 0 1 1 &
--------
0 0 0 0 <--- kontynuuj
1 0 0 0
0 1 0 1 &
--------
0 0 0 0 <----- kontynuuj
1 0 0 0
1 0 0 1 &
--------
1 0 0 1 <----- koniec, były 3 zeraTak naprawdę to 1 nie jest nam potrzebne poza pierwszym obrotem, ale tak mi się napisało, więc to zrobimy:
function countTrailingZeros(num){
let cnt = 0;
let pow = 1;
let flag= 1;
while((num & flag) === 0){
cnt++;
flag = 1 + Math.pow(2, pow++);
}
return cnt;
}
console.log(countTrailingZeros(8)); //3
console.log(countTrailingZeros(9)); //0No jak widać 9 ma zero zer po prawej (9 to 1001) zaś 8 aż 3 zera po prawej (8 to 1000).
Mechanizm jest taki, że flaga to na początku 1, potem 3, potem 9, potem 17. Naprawdę nie wiem, co sobie wtedy w głowie myślałem, można to dużo uprościć:
function countTrailingZeros(num){
let cnt = 0;
let pow = 1;
let flag= 1;
while((num & flag) === 0){
cnt++;
flag = Math.pow(2, pow++);
}
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)); //1Ale można to jeszcze uprościć:
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)); //1Zakładam, że jesteśmy już na tym poziomie, że nie muszę tłumaczyć co tu się dzieje, ewentualnie odesłać do papieru i długopisu, jeżeli coś jest odrobinkę niejasne.
