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

Question

Я хочу вычислить 2 ⁿ -1 для 64-битного целочисленного значения.То, что я сейчас делаю, это

for(i=0; i<n; i++) r|=1<<i;

, и мне интересно, есть ли более элегантный способ сделать это.Линия находится во внутреннем цикле, поэтому мне нужно, чтобы она была быстрой.

Я думал о

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

, но она не работает для n=64, потому что <<определяется только для значений от n до 63.

---

РЕДАКТИРОВАТЬ: Спасибо за все ваши ответы и комментарии.Вот небольшой столик с решениями, которые я попробовал и которые понравились мне больше всего.Второй столбец - это время в секундах моего (совершенно ненаучного) теста.

r=N2MINUSONE_LUT[n];            3.9 lookup table = fastest, <a href="https://stackoverflow.com/questions/3032951/how-to-calculate-2n-1-efficiently-without-overflow/3032977#3032977">answer</a> by aviraldg
r =n?~0ull>>(64 - n):0ull;      5.9 fastest without LUT, <a href="https://stackoverflow.com/questions/3032951/how-to-calculate-2n-1-efficiently-without-overflow/3033004#3033004">comment</a> by Christoph
r=(1ULL<<n)-1;                  5.9 Obvious but WRONG!   
r =(n==64)?-1:(1ULL<<n)-1;      7.0 Short, clear and quite fast, <a href="https://stackoverflow.com/questions/3032951/how-to-calculate-2n-1-efficiently-without-overflow/3033004#3033004">answer</a> by Gabe
r=((1ULL<<(n/2))<<((n+1)/2))-1; 8.2 Nice, w/o spec. case, <a href="https://stackoverflow.com/questions/3032951/how-to-calculate-2n-1-efficiently-without-overflow/3033900#3033900">answer</a> by drawnonward
r=(1ULL<<n-1)+((1ULL<<n-1)-1);  9.2 Nice, w/o spec. case, <a href="https://stackoverflow.com/questions/3032951/how-to-calculate-2n-1-efficiently-without-overflow/3033033#3033033">answer</a> by David Lively
r=pow(2, n)-1;               99.0 Just for comparison
for(i=0; i<n; i++) r|=1<<i;   123.7 My original solution = lame

Я принял

r =n?~0ull>>(64 - n):0ull;

в качестве ответа, потому что, на мой взгляд, это самое элегантное решение.Сначала это было Кристоф , но, к сожалению, он опубликовал это только в комментарии . Jens Gustedt добавил действительно хорошее обоснование, поэтому я принимаю его ответ вместо этого.Поскольку мне понравилось справочная таблица Aviral Dasgupta решение , он получил 50 очков репутации за вознаграждение.

Answer 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,
};

Answer 2

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

Answer 3

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

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

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

Answer 4

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

if (n == 64)
  return 0xFFFFFFFFFFFFFFFFULL;

return (1ULL << n) - 1;

Answer 5

Мне больше всего нравится aviraldg. Просто чтобы избавиться от "ULL" и т. Д. В C99, я бы сделал

static inline uint64_t n2minusone(unsigned n) {
   return n ? (~(uint64_t)0) >> (64u - n) : 0;
}

Чтобы убедиться, что это действительно

• a uint64_t гарантированно имеет ширину ровно 64 бита
• битовое отрицание того, что `ноль типа uint64_t 'имеет, таким образом, точно 64 бита
• смещение вправо без знака значения гарантированно будет логичным сдвиг, так что все заполнено нулями слева
• Смещение со значением, равным или большим ширины, не определено, поэтому да, вы должны выполнить хотя бы одно условие, чтобы быть уверенным в своем результате
• встроенная функция (или, в качестве альтернативы, приведение к uint64_t, если вы предпочитать) делает этот тип безопасным; unsigned long long мая в будущем это будет 128-битное значение
• a static inline функция должна быть бесшовной вписывается в звонилку без накладных расходов

Answer 6

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

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

Answer 7

Смещение 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))

checkесли это может быть упрощено ... конечно, n> 0

РЕДАКТИРОВАТЬ

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

__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» и 0xFFFFF, случайно 52 и 31 = 20 и, конечно, n = 20 дает 0xFFFFF ...

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

Answer 8

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

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

Answer 9

Я ненавижу, что (а) n << 64 не определено и (б) на популярном аппаратном обеспечении 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;
}

Answer 10

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

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

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

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