Приведение unsigned int к unsigned short int с помощью битового оператора

Question

Я бы хотел привести беззнаковое целое (32 бита) A к беззнаковому короткому целому (16 бит) B следующим образом:

• если A <= 2 ^ 16-1, то B = A </li>
• если A> 2 ^ 16-1, то B = 2 ^ 16-1

Другими словами, для приведения A, но если оно> максимально допустимого значения для 16 бит, чтобы установить его как максимальное значение.

Как этого добиться с помощью битовых операций или другого не ветвящегося метода?

Answer 1

Будет работать для беззнаковых значений:

b = -!!(a >> 16) | a;

или что-то похожее:

static inline unsigned short int fn(unsigned int a){
    return (-(a >> 16) >> 16) | a;
};

Answer 2

Найти не менее двух целых чисел без ветвления:

http://graphics.stanford.edu/~seander/bithacks.html#IntegerMinOrMax

На некоторых редких машинах, где ветвление очень дорого и не существует инструкций перемещения условия, приведенное выше выражениебыстрее, чем очевидный подход, г = (х <у)?x: y, хотя он включает в себя еще две инструкции.(Как правило, очевидный подход лучше, хотя.) </p>

Просто для начала, вот эталонный тест.Я пытаюсь получить смесь 50/50 больших и малых значений «случайным образом»:

#include <iostream>
#include <stdint.h>

int main() {
    uint32_t total = 0;
    uint32_t n = 27465;
    for (int i = 0; i < 1000*1000*500; ++i) {
        n *= 30029; // worst PRNG in the world
        uint32_t a = n & 0x1ffff;
        #ifdef EMPTY
            uint16_t b = a; // gives the wrong total, of course.
        #endif
        #ifdef NORMAL
            uint16_t b = (a > 0xffff) ? 0xffff : a;
        #endif
        #ifdef RUSLIK
            uint16_t b = (-(a >> 16) >> 16) | a;
        #endif
        #ifdef BITHACK
            uint16_t b = a ^ ((0xffff ^ a) & -(0xffff < a));
        #endif
        total += b;
    }
    std::cout << total << "\n";
}

На моем компиляторе (gcc 4.3.4 на cygwin с -O3), NORMAL побед,затем RUSLIK, затем BITHACK, соответственно на 0,3, 0,5 и 0,9 секунды медленнее, чем пустой цикл.На самом деле этот тест ничего не значит, я даже не проверил испущенный код, чтобы увидеть, достаточно ли умен компилятор, чтобы меня где-то перехитрить.Но мне все равно нравится Руслик.

Answer 3

Прежде всего, фраза «метод без ветвления» технически не имеет смысла при обсуждении кода C; оптимизатор может найти способы удалить ветки из «ветвистого» кода C и, наоборот, будет полностью в своих правах заменить ваш умный, не ветвящийся код веткой, просто чтобы вас злить (или потому что некоторые эвристики говорят, что это будет быстрее).

Кроме этого, простое выражение:

uint16_t b = a > UINT16_MAX ? UINT16_MAX : a;

, несмотря на то, что «имеет ветвь», будет скомпилирован с некоторым (без ветвления) условным перемещением (или, возможно, просто насыщенным) многими компиляторами на многих системах (я только что попробовал три разных компилятора для ARM и Intel, все сгенерировали условный ход).

Я бы использовал это простое, читаемое выражение. Если и только если ваш компилятор не достаточно умен, чтобы оптимизировать его (или ваша целевая архитектура не имеет условных перемещений), и если у вас есть контрольные данные, которые показывают, что это является узким местом для вашей программы, то я бы (а) найдите лучший компилятор и (b) сообщите об ошибке вашему компилятору, а только тогда поищите хитрые хаки.

Если вы действительно, действительно посвящаете себя тому, чтобы быть слишком умным наполовину, то второе предложение ruslik на самом деле довольно красиво (гораздо приятнее, чем общий мин / макс).

Answer 4

1) При наличии встроенного процессора, который изначально выполняет этот тип преобразования.

2) Возможно, вам это не понравится, но:

c = a >> 16; /* previously declared as a short */
/* Saturate 'c' with 1s if there are any 1s, by first propagating
1s rightward, then leftward. */
c |= c >> 8;
c |= c >> 4;
c |= c >> 2;
c |= c >> 1;
c |= c << 1;
c |= c << 2;
c |= c << 4;
c |= c << 8;
b = a | c; /* implicit truncation */