Обнаружение одиночных однобитовых потоков внутри целого числа

Question

Я должен проверить число, если оно удовлетворяет следующим критериям:

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

Я написал код, который проверяет эти условия на наличие реальной проблемы (проверка целостности файла данных).

Работает без проблем и совсем не критично ко времени, но я старый урод, немного перепутанный, и мне нравятся такие головоломки, поэтому я попытался найти более умный способ проверить наличие одного-одного-одного. битовые потоки.

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

Любые идеи, бинарные взломы и частичные решения приветствуются!

---

Чтобы прояснить мои требования, приведу несколько примеров: Следующие цифры соответствуют моим критериям:

  0x80000000
  0x00000001
  0xff000000
  0x000000ff
  0xffffffff
  0x000ff000

Следующие числа не имеют (поскольку они имеют более одной последовательной строки из них):

  0xf00000f <- one-bit streams should not wrap-around at 2^n
  0x0001700 <- a trivial example.
  0x0000000 <- no one bit at all.

Answer 1

Это должно делать то, что вы хотите.

if(i == 0)
    return false;
while(i % 2 == 0) {
    i = i / 2;
}
return (i & (i + 1)) == 0;

Answer 2

bool isOK(uint val) {
   while (val != 0 && (val & 1u) == 0) val >>= 1;
   if (val == 0) return false;
   while (val != 0 && (val & 1u) == 1) val >>= 1;
   return val == 0;
}

; x86 assembly
mov eax, THE_NUMBER ; store the number in eax
bsf ecx, eax
jz .notok
mov edi, 1
shl edi, cl
mov esi, eax
add esi, edi
test esi, eax
jnz .notok
mov eax, 1
jmp .end
.notok:
mov eax, 0
.end: ; eax = 1 if satisfies the criteria, otherwise it's 0

Answer 3

Я решил почти ту же проблему там http://smallissimo.blogspot.fr/2012/04/meteor-contest-part-3-reducing.html в методе hasInsetZero: (и использовал несколько других битовых трюков)

hasInsetZero: aMask
    | allOnes |
    allOnes := aMask bitOr: aMask - 1.
    ^(allOnes bitAnd: allOnes + 1) > 0

Это код Smalltalk, но переведенный на C (нам нужно отрицание и забота о 0), это будет:

int all_set_bits_are_consecutive( x )
/* return non zero if at least one bit is set, and all set bits are consecutives */
{
   int y = x | (x-1);
   return x && (! (y & (y+1)));
}

Answer 4

Моя рабочая версия. Не в качестве ответа, просто чтобы дать больше идей и задокументировать мой текущий подход:

int IsSingleBitStream (unsigned int a)
{
  // isolate lowest bit:
  unsigned int lowest_bit = a & (a-1);

  // add lowest bit to number. If our number is a single bit string, this will
  // result in an integer with only a single bit set because the addition will     
  // propagate up the the highest bit. We ought to end up with a power of two.
  a += lowest_bit;

  // check if result is a power of two:
  return (!a || !(a & (a - 1)));
}

Этот код не будет работать, если строка:

a + = низший_бит

переливается. Кроме того, я не уверен, что мой «изолировать один бит» код работает, если есть более одного битового поля.

Answer 5

Я бы использовал bsr и bsf для определения минимального и максимального битов, установленных в числе. Исходя из этого, создать действительное число, которое удовлетворяет критериям. Сравните известное действительное число с фактическим числом на равенство. Никаких петель и только одно сравнение.

псевдо-код:

min_bit = bsf(number);
max_bit = bsr(number);
valid_number = ~(-1 << (max_bit - min_bit) ) << min_bit;
return ( number == valid_number );

Answer 6

Если вы хотите быстро, основной алгоритм будет:

1. Найти младший установленный бит.
2. Сдвиг числа по индексу установленного младшего бита.
3. Добавить 1.
4. Если результатом является степень двойки и ненулевое значение, успех!

Все эти операции являются либо O (1), либо O (log (целочисленная битовая ширина)) следующим образом:

unsigned int lowest_power_of_2(unsigned int value) 
{ return value & -value; }

unsigned int count_bits_set(unsigned int value) 
{ /* see counting bits set in parallel */ }

unsigned int lowest_bit_set_or_overflow_if_zero(unsigned int value)
{ return count_bits_set(lowest_power_of_2(value) - 1); }

unsigned int is_zero_or_power_of_2(unsigned int value)
{ return value && (value & (value - 1))==0; }

bool magic_function(unsigned in value)
{ return is_zero_or_power_of_2((value >> (lowest_bit_set_or_overflow_if_zero(lowest_power_of_2(value)))) + 1); }

Редактировать: обновленная конечная операция для учета нуля, но алгоритм OP намного быстрее, поскольку все это постоянная операция (хотя учет переполнения будет PITA).

MSN

Answer 7

Существует (N^2 - N) / 2 возможностей для N-разрядного целого числа (496 для 32-разрядного).

Вы можете использовать справочную таблицу.