Самый быстрый способ считать количество разрядных переходов в неподписанном интервале
Вам просто нужно изменить строку формата.
String format = "%8s%n";
Удалите один %s, поскольку вы пропускаете на одну строку меньше по сравнению с вашим примером кода, а 8 является отступом для второй строки.
Значение 8, потому что 1 tab = 8 spaces.
6 ответов
int numTransitions(int a)
{
int b = a >> 1; // sign-extending shift properly counts bits at the ends
int c = a ^ b; // xor marks bits that are not the same as their neighbors on the left
return CountBits(c); // count number of set bits in c
}
Поскольку эффективное внедрение CountBits видит http://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetParallel
Самый быстрый зависит от Вашего сценария: Когда Вы указали свой тип данных как постоянный измеренный (неподписанный интервал), это возможно со справочной таблицей. Но когда Вам нужна эта операция только однажды постоянные издержки к init, таблица является слишком большой, и scanning+counting через интервал намного быстрее несмотря на.
Я предполагаю, что полной лучшей была бы комбинация: Ищите таблицу для байта или слова (256, или 64k записи не так), и затем объедините байты/слова их последним/первым битом.
В C/C++ я сделал бы следующее:
unsigned int Transitions(unsigned int value)
{
unsigned int result = 0;
for (unsigned int markers = value ^ (value >> 1); markers; markers = markers >> 1)
{
if (markers & 0x01) result++;
}
return result;
}
Вот код с помощью арифметического сдвига + xor и метод Kernighan для разрядного подсчета:
int count_transitions(int x)
{
assert((-1 >> 1) < 0); // check for arithmetic shift
int count = 0;
for(x ^= (x >> 1); x; x &= x - 1)
++count;
return count;
}
Какой язык?
Я циклично выполнился бы 64 раза и затем сдвиг разряда Ваше число для осмотра битов, затем сохранил бы предыдущий бит и сравнил бы его с текущим. Если это отличается, incremember Ваше количество.
Хорошо, с переходами Вы имеете в виду, идете ли Вы через строку 0-s и 1-s, Вы считаете каждое происшествие, что 0 следует за 1, или 1 следует за 0.
Это легко путем переключения битов на верхний регистр и подсчета изменений:
transitions(n)
result = 0
prev = n mod 2
n = n div 2
while n<>0
if n mod 2 <> prev then
result++
prev = n mod 2
fi
n = n div 2
elihw
return result
можно заменить модификацию и отделение со сдвигами.