Как вычислить 2^n-1 эффективно без переполнения?

Используйте таблицу поиска. (Сгенерировано вашим текущим кодом.) Это идеально, поскольку количество значений невелико, и вы уже знаете результаты.

/* lookup table: n -> 2^n-1 -- do not touch */
const static uint64_t N2MINUSONE_LUT[] = {
0x0,
0x1,
0x3,
0x7,
0xf,
0x1f,
0x3f,
0x7f,
0xff,
0x1ff,
0x3ff,
0x7ff,
0xfff,
0x1fff,
0x3fff,
0x7fff,
0xffff,
0x1ffff,
0x3ffff,
0x7ffff,
0xfffff,
0x1fffff,
0x3fffff,
0x7fffff,
0xffffff,
0x1ffffff,
0x3ffffff,
0x7ffffff,
0xfffffff,
0x1fffffff,
0x3fffffff,
0x7fffffff,
0xffffffff,
0x1ffffffff,
0x3ffffffff,
0x7ffffffff,
0xfffffffff,
0x1fffffffff,
0x3fffffffff,
0x7fffffffff,
0xffffffffff,
0x1ffffffffff,
0x3ffffffffff,
0x7ffffffffff,
0xfffffffffff,
0x1fffffffffff,
0x3fffffffffff,
0x7fffffffffff,
0xffffffffffff,
0x1ffffffffffff,
0x3ffffffffffff,
0x7ffffffffffff,
0xfffffffffffff,
0x1fffffffffffff,
0x3fffffffffffff,
0x7fffffffffffff,
0xffffffffffffff,
0x1ffffffffffffff,
0x3ffffffffffffff,
0x7ffffffffffffff,
0xfffffffffffffff,
0x1fffffffffffffff,
0x3fffffffffffffff,
0x7fffffffffffffff,
0xffffffffffffffff,
};

Если вы хотите получить максимальное значение непосредственно перед переполнением с заданным количеством битов, попробуйте

r=(1ULL << n-1)+((1ULL<<n-1)-1);

Разделив сдвиг на две части (в данном случае два 63-битных сдвига, поскольку 2 ^ 64 = 2 * 2 ^ 63), вычитая 1 и затем складывая два результата вместе, вы сможете выполнить расчет без переполнения 64-битного типа данных.

Единственная проблема в том, что ваше выражение не определено для n = 64? Тогда частный случай, что одно значение.

(n == 64 ? 0ULL : (1ULL << n)) - 1ULL

Ненавижу, что (a) n << 64 не определено и (b) на популярном оборудовании Intel смещение по размеру слова не работает.

Сюда можно перейти тремя способами:

1. Таблица поиска. Я не рекомендую этого делать из-за трафика памяти, плюс вы напишете много кода для поддержания трафика памяти.

2. Условная ветвь. Проверьте, равен ли n размеру слова ( 8 * sizeof (unsigned long long) ), если да, верните ~ (unsigned long long) 0 , в противном случае сдвигайте и вычитайте как обычно.

3. Попытайтесь стать умнее с арифметикой. Например, в вещественных числах 2 ^ n = 2 ^ (n-1) + 2 ^ (n-1) , и вы можете использовать эту идентичность, чтобы никогда не использовать степень, равную слову размер. Но вам лучше быть очень уверенным, что n никогда не равно нулю, потому что если это так, то это тождество не может быть выражено целыми числами, и сдвиг влево на -1 может укусить вас под зад.

Я лично выбрал бы условный переход - его сложнее всего испортить, он явно обрабатывает все разумные случаи n , а с современным оборудованием вероятность неверного предсказания перехода мала. Вот что я делаю в своем реальном коде:

/* What makes things hellish is that C does not define the effects of
   a 64-bit shift on a 64-bit value, and the Intel hardware computes
   shifts mod 64, so that a 64-bit shift has the same effect as a
   0-bit shift.  The obvious workaround is to define new shift functions 
   that can shift by 64 bits. */

static inline uint64_t shl(uint64_t word, unsigned bits) {
  assert(bits <= 64);
  if (bits == 64)
    return 0;
  else
    return word << bits;
}

Поскольку вы просили элегантный способ сделать это:

const uint64_t MAX_UINT64 = 0xffffffffffffffffULL;
#define N2MINUSONE(n) ((MAX_UINT64>>(64-(n))))

Верно, что в C каждая операция сдвига битов должна сдвигаться на меньшее количество битов, чем имеется бит в операнде (в противном случае поведение не определено). Однако никто не запрещает вам выполнять смену в два последовательных шага

r = ((1ULL << (n - 1)) << 1) - 1;

Т.е. сначала сдвиньте на n - 1 бит, а затем сделайте дополнительный сдвиг на 1 бит. В этом случае, конечно, вы должны обработать ситуацию n == 0 особым образом, если это допустимый ввод в вашем случае.

В любом случае он лучше вашего для цикла. Последнее - это, по сути, та же идея, но по какой-то причине доведенная до крайности.

Сдвиг 1 << 64 в 64-битном целом дает 0, так что нет необходимости вычислять что-либо для n > 63; сдвиг должен быть достаточно быстрым

r = n < 64 ? (1ULL << n) - 1 : 0;

Но если вы пытаетесь таким образом узнать максимальное значение, которое может иметь N-битное беззнаковое целое, вы меняете 0 на известное значение, рассматривая n == 64 как особый случай (и вы не сможете дать результат для n > 64 на оборудовании с 64-битными целыми числами, если не используете библиотеку multiprecision/bignumber).

Другой подход с битовыми трюками

~-(1ULL << (n-1) ) | (1ULL << (n-1))

Проверьте, можно ли его семплифицировать... конечно, n>0

EDIT

Тесты, которые я сделал

__attribute__((regparm(0))) unsigned int calcn(int n)
{
  register unsigned int res;
  asm(
    "  cmpl $32, %%eax\n"
    "  jg   mmno\n"
    "  movl $1, %%ebx\n"      // ebx = 1
    "  subl $1, %%eax\n"      // eax = n - 1
    "  movb %%al, %%cl\n"     // because of only possible shll reg mode
    "  shll %%cl, %%ebx\n"    // ebx = ebx << eax
    "  movl %%ebx, %%eax\n"   // eax = ebx
    "  negl %%ebx\n"          // -ebx
    "  notl %%ebx\n"          // ~-ebx
    "  orl  %%ebx, %%eax\n"   // ~-ebx | ebx
    "  jmp  mmyes\n"
    "mmno:\n"
    "  xor %%eax, %%eax\n"
    "mmyes:\n"
    :
    "=eax" (res):
    "eax" (n):
    "ebx", "ecx", "cc"
    );
  return res;
}

#define BMASK(X) (~-(1ULL << ((X)-1) ) | (1ULL << ((X)-1)))
int main()
{
  int n = 32; //...
  printf("%08X\n", BMASK(n));
  printf("%08X %d %08X\n", calcn(n), n&31, BMASK(n&31));
  return 0;
}

Выход с n = 32 - -1 и -1, в то время как n = 52 дает "-1" и 0xFFFF, случайно 52&31 = 20 и, конечно, n = 20 дает 0xFFFF...

EDIT2 теперь asm код выдает 0 для n > 32 (так как я на 32 битной машине), но на данный момент решение a ? b : 0 с BMASK более понятно и я сомневаюсь, что asm решение намного быстрее (если скорость так важна, то идея с таблицей может быть быстрее).

Как насчет простого r = (n == 64)? -1: (1ULL << n) -1; ?

if (n > 64 || n < 0)
  return undefined...

if (n == 64)
  return 0xFFFFFFFFFFFFFFFFULL;

return (1ULL << n) - 1;

Я думаю, что проблема, которую вы наблюдаете, вызвана тем, что (1< оценивается как (1<<(n%64))-1 на некоторых чипах. Особенно если n является или может быть оптимизировано как константа.

((1ULL<<(n/2))<<((n+1)/2))-1;

(n<64)?(1ULL<<n)-1:~0ULL;