Битовые головоломки
Давненько я тут не писал, совсем разленился… Решил написать о чём болит голова второй день…
Всё началось с того, что решил подумать, как ускорить перебор среди элементов со множеством полей. Можно по каким-то полям сделать индекс, но покрыть индексами всё не получается. Таким образом, в некоторых случаях, придётся использовать тупой перебор.
Первое что приходит в голову для ускорения перебора — использование битовых операций. Сформировал маску и пошёл AND-ом по списку, красота. Но когда наткнулся на необходимость проверить что значение больше (или меньше) заданного, впал в ступор. Если диапазон значений меньше или равен количеству бит в целом, никаких проблем нет, а если диапазон шире, ступор.
Вот скажите, это я такой тупой, или стандартными логическими операциями нельзя проверить что одно число больше другого?
Tags: битовые операции, программирование
c = (a & b ) | ~(a ^ b)
если c < 0, то а 0, a > b, ну и равны если 0
ах да, можно до усрачки проверять на больше/меньше.
через рекуррентную функцию
int rch(int a, int b) {
c = (a & b ) | ~(a ^ b)
return rch(c, 0);
}
и мля, настрой теги нормально, весь текст корявит
Вариант, но не практично, 4 битовых операции и одна логическая, многова-то
Многова-то….
ну упростим… делоф-то
int rch(int a, int b) {return ( a & ~b );
}
Если результат меньше 0, то а b;
Честно говоря не вкуриваю смысл затеи.
Ниже только асм и транзисторы.
На С, по любому в if упрёшся, тогда нафиг всё это нужно…
просто if ( a < b )
На асме
mov ax, $a
mov bx, $b
cmp ax, bx
jnle :nazad
2-ой вариант
mov ax, $a
mov bx, $b
not bx
and ax, bx;
jnle :nazad
надо смотреть таблицу растактовок что быстрее not + and или cmp
Ну это давние размышления. Идея была в следующем. Бывают задачи, когда единственный способ что-то найти — это перебор. Например, поиск в знакомствах, социалках и т.п., когда полей, по которым осуществляется поиск много. Так вот была идея осуществлять поиск битовыми операциями. Больше-меньше необходимо было для определения попадания возраста в диапазон, но я потом решил просто выделить 64-бит число мод возрастную маску с 16 до 80 лет, тогда search_age_mask & user_age_mask в одну операцию определяют попадание возраста в диапазон.
В конце концов мне посоветовали “мыслить перпендикулярно”