Учитывая целое число, как я нахожу следующее самое большое питание двух битового жонглирования использования?
НЕТ! та пустая проверка избыточна. Партия C++ devs, кто переместился в C#, имеет эту привычку к пустой проверке, и я предполагаю, что это - то же здесь.
единственная вещь - Вы, должен проверить документацию, чтобы видеть, может ли конструктор выдать какое-либо исключение. В Вашем случае относятся к http://msdn.microsoft.com/en-us/library/xx3ezzs2.aspx , и, как упомянуто конструктор будет всегда возвращать допустимый obj.
8 ответов
Для 32-битных целых чисел это простой и понятный путь:
unsigned int n;
n--;
n |= n >> 1; // Divide by 2^k for consecutive doublings of k up to 32,
n |= n >> 2; // and then or the results.
n |= n >> 4;
n |= n >> 8;
n |= n >> 16;
n++; // The result is a number of 1 bits equal to the number
// of bits in the original number, plus 1. That's the
// next highest power of 2.
Вот более конкретный пример. Возьмем число 221, которое в двоичном формате равно 11011101:
n--; // 1101 1101 --> 1101 1100
n |= n >> 1; // 1101 1100 | 0110 1110 = 1111 1110
n |= n >> 2; // 1111 1110 | 0011 1111 = 1111 1111
n |= n >> 4; // ...
n |= n >> 8;
n |= n >> 16; // 1111 1111 | 1111 1111 = 1111 1111
n++; // 1111 1111 --> 1 0000 0000
В девятой позиции есть один бит, который представляет 2 ^ 8, или 256, что действительно является следующей по величине степенью двойки . Каждый из сдвигов перекрывает все существующие 1 бит в числе с некоторыми из ранее не затронутых нулей, в конечном итоге создавая количество 1 бит, равное количеству бит в исходном числе. Добавление единицы к этому значению дает новую степень 2.
Другой пример; мы будем использовать 131, что равно 10000011 в двоичном формате:
n--; // 1000 0011 --> 1000 0010
n |= n >> 1; // 1000 0010 | 0100 0001 = 1100 0011
n |= n >> 2; // 1100 0011 | 0011 0000 = 1111 0011
n |= n >> 4; // 1111 0011 | 0000 1111 = 1111 1111
n |= n >> 8; // ... (At this point all bits are 1, so further bitwise-or
n |= n >> 16; // operations produce no effect.)
n++; // 1111 1111 --> 1 0000 0000
И действительно, 256 - это следующая по величине степень 2 из 131.
Если количество битов, используемых для представления целого числа, само является степенью 2,
Вам просто нужно найти самый старший бит и один раз сдвинуть его влево. Вот реализация Python. Я думаю, что у x86 есть инструкция для получения MSB, но здесь я реализую все это на прямом Python. Когда у вас есть MSB, это легко.
>>> def msb(n):
... result = -1
... index = 0
... while n:
... bit = 1 << index
... if bit & n:
... result = index
... n &= ~bit
... index += 1
... return result
...
>>> def next_pow(n):
... return 1 << (msb(n) + 1)
...
>>> next_pow(1)
2
>>> next_pow(2)
4
>>> next_pow(3)
4
>>> next_pow(4)
8
>>> next_pow(123)
128
>>> next_pow(222)
256
>>>
А что насчет такого:
int pot = 1;
for (int i = 0; i < 31; i++, pot <<= 1)
if (pot >= x)
break;
function Pow2Thing(int n)
{
x = 1;
while (n>0)
{
n/=2;
x*=2;
}
return x;
}
Here's a wild one that has no loops, but uses an intermediate float.
// compute k = nextpowerof2(n)
if (n > 1)
{
float f = (float) n;
unsigned int const t = 1U << ((*(unsigned int *)&f >> 23) - 0x7f);
k = t << (t < n);
}
else k = 1;
This, and many other bit-twiddling hacks, including the on submitted by John Feminella, can be found here.
Вот логический ответ:
function getK(int n)
{
int k = 1;
while (k < n)
k *= 2;
return k;
}
Более математический способ, без циклов:
public static int ByLogs(int n)
{
double y = Math.Floor(Math.Log(n, 2));
return (int)Math.Pow(2, y + 1);
}
There is actually a assembly solution for this (since the 80386 instruction set).
You can use the BSR (Bit Scan Reverse) instruction to scan for the most significant bit in your integer.
bsr scans the bits, starting at the most significant bit, in the doubleword operand or the second word. If the bits are all zero, ZF is cleared. Otherwise, ZF is set and the bit index of the first set bit found, while scanning in the reverse direction, is loaded into the регистр назначения
(извлечено из: http://dlc.sun.com/pdf/802-1948/802-1948.pdf )
И затем прибавьте результат к 1.
так:
bsr ecx, eax //eax = number
jz @zero
mov eax, 2 // result set the second bit (instead of a inc ecx)
shl eax, ecx // and move it ecx times to the left
ret // result is in eax
@zero:
xor eax, eax
ret
В новых процессорах вы можете использовать гораздо более быструю инструкцию lzcnt (также известную как rep bsr ). lzcnt выполняет свою работу за один цикл.