Битовая операция в C++ (n < max_n, тогда n; n == max_n, тогда 0;)

Question

[askogorev]

Добрый вечер, можно ли с помощью битовых операций реализовать следующее?

Есть n и max_n. Можно ли как-то наложить маску или еще что, чтобы когда:
n < max_n, тогда n;
n >= max_n, тогда 0;

Comments

[Ocelot]

А когда (n > max_n), тогда что?

[askogorev]

n >= max_n, тогда 0

Answer 1

[jcmvbkbc]

Например так (взял тип фиксированной ширины для простоты):

int32_t cap(int32_t n, int32_t max_n)
{
    return n & ((n - max_n) >> 31);
}

Comments

[Teivaz]

а зачем "n & "?

[Teivaz]

А, я понял, там должно быть && вместо &

[jcmvbkbc]

Нет, там должно быть именно &

[jcmvbkbc]

...и компилятор (gcc -O2) делает вот что:

cap:
.LFB0:
movl %edi, %eax # взял n
subl %esi, %eax # вычел из него n_max
sarl $31, %eax # сдвинул арифметически результат
andl %edi, %eax # побитово умножил
ret

[Teivaz]

Ну по логике берём разность (n - max_n), сдвигаем знаковый бит в младший разряд. Получаем битовую маску 0000 0000 0000 0001(ноликов будет побольше) если результат отрицательный и побитово перемножаем с числом n. Таким образом получим 1 если n нечётное (имеет 1 в младшем разряде) и 0 если четное. Если результат положительный, то возвращаем 0. ЧЯДНТ?

[jcmvbkbc]

> ЧЯДНТ?
Вы не так сдвигаете знаковый бит. При арифметическом сдвиге вправо копируется старший (знаковый) бит а не 0.

[Teivaz]

Воу, точно. Я как-то провтыкал этот момент. Спасибо.

[Teivaz]

Для беззнакового типа будет использована комманда shr, которая скопирует нолики. А вот для знакового будет sar, на которую я не обратил внимание в листинге. Видимо я просто не натыкался на этот нюанс.

[Ilya Evseev]

Я бы в порядке занудства написал не 31, а (sizeof(n)*8 - 1)

[jcmvbkbc]

@IlyaEvseev Я бы в порядке занудства написал (sizeof(n) * CHAR_BITS - 1), если бы не написал уже, что взял тип фиксированной ширины для простоты.

Answer 2

[Teivaz]

Если делать это для ускорения проверки условия, то имеет смысл когда n_max степень двойки.
тогда максимальное значение будет выглядеть, например, так:
0010 0000
Любое число, которое больше чем n_max, будет иметь единицу в одном из старших разрядов.
Тогда при наложении маски:
1110 0000
мы получим либо ноль (когда число меньше макисмального), либо некоторое значение (когда число больше или равно).
Но это не имеет особого смысла, поскольку сравнение скомпилируется в две операции (если не считать перебрасывания значений из регистра в регистр) по такту каждая: вычитание из максимального значения текущего и проверка флага отрицательности результат вычитания.

Comments

[Teivaz]

и выглядеть это будет так:

int Constraint(int n_max, int n)
{
    return (n < n_max) ? n : 0;
}

А компилятор с оптимизацией сделает следующее:
xor ecx, ecx  ; загрузит нолик в регистр ecx
mov edx, dword ptr [n]  ; загрузит переменную
mov eax, dword ptr [n_max]  ; загрузит максимальное значение
cmp edx, eax  ; сравнит их
сmovl ecx, edx  ; скопирует в регистр ecx значение переменной если результат предыдущей операции - меньше
mov dword ptr [n], ecx  ; загрузит значение в переменную

Answer 3

[xanep]

Если это в академических целях, то jcmvbkbc ответил.
Но в реальном приложении такое не стоит делать никогда. Оптимизацию нынешние компиляторы делают хорошо, даже если вы выиграете одну инструкцию, это не сделает ваше приложение быстрее. А вот нечитаемости добавит ого-го как.

Comments

[Trrrrr]

Если важно то не сделает, кучу раз приходилось в играх под иксбокс делать такие оптимизации с условными переходами. В данный момент занимаюсь написанием физики, и такие оптимизации реально помогают.

Answer 4

[Trrrrr]

Главная идея простая:
пусть есть

if (a < b) 
{
x = f(1); 
}
else
{
x = f(2);
}

это можно заменить так:
f1 = f(1);
f2 = f(2);
mask = (a < b) * 0xFFFFFFFF;/// это просто упрощенный пример, что бы вернуть или 0 или 0xFFFFFFFF

//тогда 
x = (mask & f1) | (~mask & f2);

Если f1 и f2 вычисляются быстро, то получаем выгоду за счет конвейерной архитектуры процессора. Так как условный переход у нас исчезает. Но если f - тяжелая функция, то скорее всего будет намного быстрее проверить иф и посчитать только один из вариантов.

Правда чаще всего такое делал работая с SSE2.

Answer 5

[Сергей Протько]

один вопрос... зачем? это решается тернальным оператором, и никаких извращений... или же функции вроде max/min.