Установить последние `n` биты в неподписанном int

Question

Как установить (самым элегантным образом) точно n младшие значащие биты uint32_t? То есть написать функцию void setbits(uint32_t *x, int n);. Функция должна обрабатывать каждый n от 0 до 32.

Особенно значение n==32 должно быть обработано.

Answer 1

Если вы имели в виду младшие значащие n битов:

((uint32_t)1 << n) - 1

На большинстве архитектур это не будет работать, если n равно 32, поэтому вам, возможно, придется сделать специальный случай для этого:

n == 32 ? 0xffffffff : (1 << n) - 1

В 64-битной архитектуре (возможно) более быстрое решение заключается в том, чтобы затем уменьшить число:

(uint32_t)(((uint64_t)1 << n) - 1)

На самом деле, это может быть даже быстрее в 32-битной архитектуре, поскольку избегает ветвления.

Answer 2

Вот метод, который не требует арифметики:

~(~0 << n)

Answer 3

Другие ответы не обрабатывают особый случай n == 32 (сдвиг больше или равен ширине шрифта - UB), так что вот лучший ответ:

(uint32_t)(((uint64_t)1 << n) - 1)

В качестве альтернативы:

(n == 32) ? 0xFFFFFFFF : (((uint32_t)1 << n) - 1)

Answer 4

const uint32_t masks[33] = {0x0, 0x1, 0x3, 0x7 ...

void setbits(uint32_t *x, int n)
{
   *x |= masks[n];
}

Answer 5

((((1 << (n - 1)) - 1) << 1) | 1)

Установить последние n бит.n должно быть> 0. Работа с n = 32.

Answer 6

Цели:

• нет веток (включая проверку параметров n)
• нет 64-битных преобразований

void setbits(uint32_t *x, unsigned n) {
    // As @underscore_d notes in the comments, this line is
    // produces Undefined Behavior for values of n greater than
    // 31(?). I'm ok with that, but if you're code needs to be
    // 100% defined or you're using some niche, little-used
    // compiler (perhaps for a microprocesser?), you should
    // use `if` statements. In fact, this code was just an
    // an experiment to see if we could do this in only 32-bits
    // and without any `if`s. 
    *x |= (uint32_t(1) << n) - 1;
    // For any n >= 32, set all bits. n must be unsigned
    *x |= -uint32_t(n>=32);
}

Примечание: если вам нужно, чтобы n имел тип int, добавьте это в конец:

    // For any n<=0, clear all bits
    *x &= -uint32_t(n>0);

Пояснение:

    *x |= -uint32_t(n>=32);

Когда n>=32 имеет значение true, x будет поразрядно-ИЛИ с 0xFFFFFFFF, давая x со всеми установленными битами.

    *x &= -uint32_t(n>0);

В этой строке указывается, что при установке любого бита, n>0, поразрядно-И x с 0xFFFFFFFF, что не приведет к изменению x. Если n<=0, x будет поразрядно-И с 0 и, следовательно, приведет к значению 0.

Пример программы для работы алгоритма:

#include <stdio.h>
#include <stdint.h>

void print_hex(int32_t n) {
  uint32_t x = (uint32_t(1) << n);
  printf("%3d:  %08x  |%08x  |%08x  &%08x\n",
         n, x, x - 1,
         -uint32_t(n>=32),
         -uint32_t(n>0));
}

void print_header() {
  //        1:  00000002  |00000001  |00000000  &ffffffff
  printf("  n:   1 << n    (1<<n)-1   n >= 32     n <= 0\n");
}

void print_line() {
  printf("---------------------------------------------\n");
}

int main() {
  print_header();
  print_line();
  for (int i=-2; i<35; i++) {
    print_hex(i);
    if (i == 0 || i == 31) {
      print_line();
    }
  }
  return 0;
}

Вывод (разбит и аннотирован):

Для n < = 0 последний шаг И с 0, гарантирующий результат, равен 0.

  n:   1 << n    (1<<n)-1   n >= 32     n <= 0
---------------------------------------------
 -2:  40000000  |3fffffff  |00000000  &00000000
 -1:  80000000  |7fffffff  |00000000  &00000000
  0:  00000001  |00000000  |00000000  &00000000

Для 1 <= n <= 31 последние два шага «ИЛИ 0, И 0xffffffff» не приводят к изменению числа. Единственный важный шаг - «ИЛИ (1 <

  n:   1 << n    (1<<n)-1   n >= 32     n <= 0
---------------------------------------------
  1:  00000002  |00000001  |00000000  &ffffffff
  2:  00000004  |00000003  |00000000  &ffffffff
  3:  00000008  |00000007  |00000000  &ffffffff
  4:  00000010  |0000000f  |00000000  &ffffffff
  5:  00000020  |0000001f  |00000000  &ffffffff
  6:  00000040  |0000003f  |00000000  &ffffffff
  7:  00000080  |0000007f  |00000000  &ffffffff
  8:  00000100  |000000ff  |00000000  &ffffffff
  9:  00000200  |000001ff  |00000000  &ffffffff
 10:  00000400  |000003ff  |00000000  &ffffffff
 11:  00000800  |000007ff  |00000000  &ffffffff
 12:  00001000  |00000fff  |00000000  &ffffffff
 13:  00002000  |00001fff  |00000000  &ffffffff
 14:  00004000  |00003fff  |00000000  &ffffffff
 15:  00008000  |00007fff  |00000000  &ffffffff
 16:  00010000  |0000ffff  |00000000  &ffffffff
 17:  00020000  |0001ffff  |00000000  &ffffffff
 18:  00040000  |0003ffff  |00000000  &ffffffff
 19:  00080000  |0007ffff  |00000000  &ffffffff
 20:  00100000  |000fffff  |00000000  &ffffffff
 21:  00200000  |001fffff  |00000000  &ffffffff
 22:  00400000  |003fffff  |00000000  &ffffffff
 23:  00800000  |007fffff  |00000000  &ffffffff
 24:  01000000  |00ffffff  |00000000  &ffffffff
 25:  02000000  |01ffffff  |00000000  &ffffffff
 26:  04000000  |03ffffff  |00000000  &ffffffff
 27:  08000000  |07ffffff  |00000000  &ffffffff
 28:  10000000  |0fffffff  |00000000  &ffffffff
 29:  20000000  |1fffffff  |00000000  &ffffffff
 30:  40000000  |3fffffff  |00000000  &ffffffff
 31:  80000000  |7fffffff  |00000000  &ffffffff

Для n >= 32 все биты должны быть установлены, и шаг «ИЛИ ffffffff» выполняет это независимо от того, что мог сделать предыдущий шаг. Шаг n <= 0 также является noop с AND ffffffff.

  n:   1 << n    (1<<n)-1   n >= 32     n <= 0
---------------------------------------------
 32:  00000001  |00000000  |ffffffff  &ffffffff
 33:  00000002  |00000001  |ffffffff  &ffffffff
 34:  00000004  |00000003  |ffffffff  &ffffffff

Answer 7

Если n равно нулю, тогда биты не должны устанавливаться на основе вопроса.

const uint32_t masks[32] = {0x1, 0x3, 0x7, ..., 0xFFFFFFFF};

void setbits(uint32_t *x, int n)
{
    if ( (n > 0) && (n <= 32) )
    {
        *x |= masks[--n];
    }
}

Answer 8

Если вы имеете в виду старшие значащие n битов:

-1 ^ ((1 << (32 - n)) - 1)

Answer 9

Функция с простым тестом:

#include <stdio.h>
#include <stdint.h>

void setbits(uint32_t *x, int n)
{
  *x |= 0xFFFFFFFF >> (32 - n);
}

int main()
{
  for (int n = 1; n <= 32; ++n)
  {
    uint32_t x = 0;
    setbits(&x, n);
    printf("%2d: 0x%08X\n", n, x);
  }
  getchar();
  return 0;
}