online - c bit shift




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

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

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

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

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

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

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

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

Я думал о

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

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

EDIT: Спасибо за все ваши ответы и комментарии. Вот маленький стол с решениями, которые я пробовал и любил лучше всего. Второй столбец - это время в секундах моего (полностью ненаучного) теста.

    
r=N2MINUSONE_LUT[n];            3.9 lookup table = fastest, answer by aviraldg
r =n?~0ull>>(64 - n):0ull;      5.9 fastest without LUT, comment 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, comment by Gabe
r=((1ULL<<(n/2))<<((n+1)/2))-1; 8.2 Nice, w/o spec. case, answer by drawnonward
r=(1ULL<<n-1)+((1ULL<<n-1)-1);  9.2 Nice, w/o spec. case, answer 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;

как ответ, потому что это, на мой взгляд, самое изящное решение. Сначала Christoph придумал это, но, к сожалению, он только разместил его в comment . Дженс Густедт добавил очень хорошее объяснение, поэтому вместо этого я принимаю его ответ. Поскольку мне понравилось решение Aviral Dasgupta для поиска, он получил 50 очков репутации через щедрость.


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

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

Как насчет простой r = (n == 64) ? -1 : (1ULL<<n)-1; r = (n == 64) ? -1 : (1ULL<<n)-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 один бит
  • правый сдвиг значения без знака гарантированно будет логическим сдвигом, поэтому все заполняется нулями слева
  • сдвиг со значением, равным или большим ширине, не определен, так что да, вы должны сделать хотя бы одно условие, чтобы быть уверенным в вашем результате
  • встроенная функция (или, альтернативно, приведение к uint64_t, если вы предпочитаете) делает этот тип безопасным; unsigned long long вполне может быть 128-битным значением в будущем
  • static inline функция должна быть легко встроена в вызывающего абонента без каких-либо накладных расходов

Сдвиг 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 a ? b : 0 с BMASK яснее, и я сомневаюсь, что решение asm слишком быстро (если скорость настолько большая, что идея таблицы может быть быстрее).


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

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

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

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

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

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

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

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




bit-manipulation