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

Ответ 1

Мне нравится aviraldg лучше. Просто, чтобы избавиться от вещей `ULL 'и т.д. На C99 я бы сделал

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

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

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

Ответ 2

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

/* 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,
};

Ответ 3

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

Ответ 4

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

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

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

Ответ 5

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

if (n == 64)
  return 0xFFFFFFFFFFFFFFFFULL;

return (1ULL << n) - 1;

Ответ 6

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

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

Ответ 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))

проверить, может ли он быть скомплектован... конечно, 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 слишком быстро (если скорость настолько большая, что идея таблицы может быть быстрее).

Ответ 8

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

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

Ответ 9

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

У вас есть три способа пойти сюда:

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

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

• Попытайтесь стать умными с арифметикой. Например, в действительных числах 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;
}

Ответ 10

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

Учитывая, что есть много незначительных вариаций, которые вы можете сделать. Например:

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

Вам нужно будет измерить, будет ли это быстрее, чем специальный корпус 64:

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

Ответ 11

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

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

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

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

Ответ 12

Ub = universe in bits = lg(U):
high(v) = v >> (Ub / 2)
low(v) = v & ((~0) >> (Ub - Ub / 2))  // Deal with overflow and with Ub even or odd