Вот небольшой вариант ответа Нины с большим количеством картинок, чтобы помочь читателю выяснить, что происходит на уровне битов.
Предварительные условия
Перед началом работы имейте в виду, что JavaScript может читать битыблагодаря префиксу 0b и попробуйте познакомиться с побитовыми операторами «и» (&) и «сдвиг вправо» (>>) (оставьте комментарий, если вам нужна помощь):
> | 0b1
< | 1
> | 0b111
< | 7
> | (7).toString(2)
< | "111"
> | 1 & 1
< | 1
> | 1 & 0
< | 0
> | (0b101 & 0b110).toString(2)
< | "100"
> | (0b100 >> 1).toString(2)
< | "10"
> | (0b100 >> 2).toString(2)
< | "1"
> | (0b100 >> 3).toString(2)
< | "0"
В выражении L & R, L часто называют «битовой картой», а R часто называют «битовой маской».Битовая карта представляет собой набор двоичных флагов (0/1, выкл. / Вкл., Ложь / истина), а битовая маска является селектором:
flags | 0000111 | 0000111 | 0000111
& mask | & 0000001 | & 0000011 | & 0100100
= subset | = 0000001 | = 0000011 | = 0000100
В двоичном числе первый бит (бит0) самый правый.Самый правый бит называется «младшим значащим битом» (LSB), самый левый бит называется «старшим значащим битом» (MSB):
> | 0b0000111 >> 0 & 1 // reads bit 0 (LSB)
< | 1
> | 0b0000111 >> 6 & 1 // reads bit 6 (MSB)
< | 0
Кодировка
Код дня:
SFTWTMS <---- read carefully
0b0000001 = 1 = Sunday
0b0000010 = 2 = Monday
0b0000100 = 4 = Tuesday
0b0001000 = 8 = Wednesday
0b0010000 = 16 = Thursday
0b0100000 = 32 = Friday
0b1000000 = 64 = Saturday
Битовая карта выбранных дней:
| SFTWTMS |
1 | 0b0000001 | Sunday
+ 2 | + 0b0000010 | + Monday
+ 4 | + 0b0000100 | + Tuesday
= 7 | = 0b0000111 | = selection
Битовая карта выбранных дней, повернутая и аннотированная:
Sat 0 drop (bit 6) <---- MSB
Fri 0 drop (bit 5)
Thu 0 drop (bit 4)
Wed 0 drop (bit 3)
Tue 1 take (bit 2)
Mon 1 take (bit 1)
Sun 1 take (bit 0) <---- LSB
Фильтрация
ЭтоАлгоритм считывает битовую карту из LSB в MSB:
for i in [0-6] do: take ith day if bitmap >> i & 1 equals 1
Длинная трасса:
SFTWTMS | S
0b0000111 >> 0 = 0b0000111 | 1
& 0b0000001 | & 1
= 0b0000001 | = 1 (take "Sun")
^ |
SFTWTM | M
0b0000111 >> 1 = 0b0000011 | 1
& 0b0000001 | & 1
= 0b0000001 | = 1 (take "Mon")
^ |
SFTWT | T
0b0000111 >> 2 = 0b0000001 | 1
& 0b0000001 | & 1
= 0b0000001 | = 1 (take "Tue")
^ |
SFTW | W
0b0000111 >> 3 = 0b0000000 | 0
& 0b0000001 | & 1
= 0b0000000 | = 0 (drop "Wed")
^ |
...
and so on until i = 6
Короткая трассировка:
0 | 0000111 SFTWTMS | take "Sun"
1 | 000011 SFTWTM | take "Mon"
2 | 00001 SFTWT | take "Tue"
3 | 0000 SFTW | drop "Wed"
4 | 000 SFT | drop "Thu"
5 | 00 SF | drop "Fri"
6 | 0 S | drop "Sat"
^ ^
Пример
Пример из реальной жизни:
> | Sun = 0b0000001
< | 1
> | Mon = 0b0000010
< | 2
> | Tue = 0b0000100
< | 4
> | bitmap = Sun + Mon + Tue
< | 7
> | days = ["Sun", "Mon", "Tue", "Wed", "Thu", "Fri", "Sat"]
< | ["Sun", "Mon", "Tue", "Wed", "Thu", "Fri", "Sat"]
> | days.filter((_, i) => bitmap >> i & 1)
< | ["Sun", "Mon", "Tue"]
Обратите внимание, что битовая карта эквивалентна массиву логических значений:
> | take = [true, true, true, false, false, false, false]
< | [true, true, true, false, false, false, false]
> | selection = []
< | []
> | for (i = 0; i < days.length; i++) {
| if (take[i]) selection.push(days[i]);
| }
| selection
< | ["Sun", "Mon", "Tue"]
И bitmap >> i & 1 («чтение i-го бита») эквивалентноtake[i] ("прочитайте элемент ih"):
> | for (i = 0; i < 7; i++) {
| console.log(i, bitmap >> i & 1, take[i]);
| }
| 0 1 true
| 1 1 true
| 2 1 true
| 3 0 false
| ...
Сравнение
Версия Нины немного отличается, действительно, я сдвигаю бит map в вправо , в то время как Нина сдвигает бит маска в влево , что возвращает разные результаты:
Me : (bitmap >> i) & 1
Nina : bitmap & (i << 1)
| bit map | & | bit mask
------|-------------|---|----------
Me | bitmap >> i | & | 1
Nina | bitmap | & | 1 << i
Моя собственная версия возвращаетсявсегда 0 или 1 (ложь / тrue, drop / take):
> | 0b0000111 >> 0 & 1 // = 0b0000111 & 0b0000001
< | 1
> | 0b0000111 >> 1 & 1 // = 0b0000011 & 0b0000001
< | 1
> | 0b0000111 >> 2 & 1 // = 0b0000001 & 0b0000001
< | 1
> | 0b0000111 >> 3 & 1 // = 0b0000000 & 0b0000001
< | 0
Версия Nina возвращает выбранный день (истинное значение, take) или 0 (ложное значение, drop):
> | 0b0000111 & 1 << 0 // = 0b0000111 & 0b0000001
< | 1
> | 0b0000111 & 1 << 1 // = 0b0000111 & 0b0000010
< | 2
> | 0b0000111 & 1 << 2 // = 0b0000111 & 0b0000100
< | 4
> | 0b0000111 & 1 << 3 // = 0b0000111 & 0b0001000
< | 0
Это нене имеет большого значения в контексте функции filter, за исключением того, что возвращение логических значений (0/1, false / true) звучит немного более согласованно.Тем не менее, с версией Нины вы можете собирать выбранные флажки так:
> | bitmap = 0b0000111
< | 7
> | checkboxes = []
< | []
> | for (i = 0; i < 7; i++) {
| day = bitmap & 1 << i;
| if (day) checkboxes.push(day);
| }
| checkboxes
< | [1, 2, 4]