Установить или Сбросить заданный бит без разветвления

в одном интервью они спросили меня: «Как вы установите или перезагрузите бит? Это очень простой вопрос, и я ответил на это.

После этого они спросили меня, сделай это without branching . Я не знаю, что такое ветвление. Я ищу это, и я пришел сюда http://graphics.stanford.edu/~seander/bithacks.html

Но все же не получилось понятие ветвления и неветвяления. Пожалуйста, объясните Branching .

Ветвление означает, что инструкции, выполняемые процессором, содержат условный скачок. Или – или выбор. Это может означать if , a for -loop, while -loop, switch , ?: Или что-то, что принимает решение на основе логического.

Один class ветвей, которые люди часто забывают, также является короткозамкнутым булевым оператором и, возможно, (но не обязательно на всех ЦП) вещами, которые оценивают значения истинности, поэтому int foo; ...; foo = !foo; int foo; ...; foo = !foo; будет ветвью на некоторых процессорах, но не все (а не на x86).

Итак, чтобы установить немного:

 i |= (1 << bit); 

Сбросить бит:

 i &= ~(1 << bit); 

Переключить бит:

 i ^= (1 << bit); 

Нет ветвей. На самом деле я не вижу, как сделать это настолько сложным, что нужно использовать ветку.

Причина, по которой кто-то может беспокоиться о ветвях, - это предсказание ветвей. См. Этот вопрос и ответ за отличное объяснение того, почему это имеет значение.

Может быть, они хотели, чтобы вы показали, как писать общий набор / сброс fragmentа без ветвей …

Это можно сделать с помощью

 value = (value & ~(1 << bit)) | (bitval << bit); 

где bit - бит, а bitval - 1 для набора и 0 для сброса.

Что-то даже немного более общее:

 value = (value & ~(k1 << bit)) ^ (k2 << bit); 

который реализует несколько операций:

  • k1=0 и k2=0 ничего не делает
  • k1=0 и k2=1 переключает бит
  • k1=1 и k2=0 очищает бит
  • k1=1 и k2=1 устанавливает бит

В более общем плане

 value = (value & a) ^ x; 

вы можете решить изменить несколько бит value одновременно

  • aj=0 , xj=0 → установив их в 0
  • aj=0 , xj=1 → установив их в 1
  • aj=1 , xj=0 → оставляя их нетронутыми
  • aj=1 , xj=1 → переворачивание их

в зависимости от предварительно вычисленных констант a и x ( aj и xj - значение j-го бита в константах).

Например

 value = (value & 0x0F) ^ 0x3C; 

с одной операцией

 - leave untouched bit 0 and 1 - flip bits 2 and 3 - set to 1 bits 4 and 5 - set to 0 all other bits