Проверка битов целых, чтобы увидеть, разделяют ли они двоичный файл со степенью 2 (только по битам)

Question

Я пытаюсь воссоздать эту функцию:

int test(int x) {
   int i;
   for (i = 0; i < 32; i+=2)
   if ((x & (1<<i)) == 0)
      return 0;
   return 1; 
}

Но используя только побитовые операторы:!, ~, &, ^, |, +, << и >> (значениебез циклов или с заявлениями)

Я так запутался в этом вопросе, что смотрю на него около часа и до сих пор не уверен, с чего начать.

Я понимаю, что в основном этоберет x, сравнивая его с 2 ^ i, где i равно 0-31, и затем возвращает 0, если x и 2 ^ i не используют одни и те же биты, и возвращает 1 в противном случае.

Но я чувствую, что есть более простое, не сфокусированное на битах объяснение, которое суммирует это лучше, и если бы кто-то мог даже дать мне, что это было бы огромной помощью.

Answer 1

Как уже было сказано, минимальное решение будет

return (x & 0x55555555) == 0x55555555 ;

Однако, здесь используется '==', которого нет в списке разрешенных операторов. Сравнение целых чисел более или менее эквивалентно тому, чтобы видеть, равна ли разница между числами ноль или нет, но «-» также отсутствует в списке разрешенных операторов, но «+» есть. Установка первого бита в целом числе со знаком равносильна тому, чтобы сделать его отрицательным и вычесть 1. Следовательно, функцию можно записать в виде:

return !(((x & 0x55555555) | 0x80000000) + 0x55555556);

Это предполагает, что ввод не отрицательный, и, похоже, также не работаетдля очень большого ввода, но работает для чисел в диапазоне от 0 до 1431655764 в моих тестах. Кроме того, здесь предполагаются 32-разрядные целые числа.

Редактирование: оператор XOR, очевидно, является гораздо более подходящей заменой '==':

return !((x & 0x55555555) ^ 0x55555555);

Работает и для отрицательных чисел!

Answer 2

Непонятно, в чем тут вопрос, но из:

Но я чувствую, что есть более простое, не сосредоточенное на битах объяснение, которое обобщает это лучше, и если бы кто-то мог даже просто датьмне, что это было бы огромной помощью.

Кажется, вы просто просите описание того, что делает код. В таком случае ваше заявленное понимание совершенно неверно. Поведение кода просто:

• Возвращает 1, если все четные пронумерованные биты равны 1, и ноль в противном случае.

Answer 3

Если вы хотите узнать, имеют ли числа одинаковую длину, вы можете использовать это:

def log2_floor(x): 
  res=-1 
  while x: 
     res+=1 
     x = x>>1 
  return res 

def compare_bitlength(hm, hm2):
   hmone = log2_floor(hm)
   hmtwo = log2_floor(hm2)
   if hmone == hmtwo:
      print (f'{hm} and {hm2} share the same bitlength of {hmone}')
   else:
      print (f'{hm} has bitlength {hmone} and {hm2} has bitlength {hmtwo} and are not the same bitlength')


In [351]: compare_bitlength(15,14)                                                                       
15 and 14 share the same bitlength of 3

Answer 4

Я думаю, что мы находимся в том же или похожих классах :). Однако, если это так, обязательно запомните, что любые цифры, которые вы используете, должны быть ниже 0xff. Таким образом, 0x55555555 должно быть (0x55 << 24) |(0x55 << 16) |(0x55 << 8) |0x55) (хотя, вероятно, есть лучший способ сделать это). </p>

У меня тот же вопрос, но у меня также есть вариант:

int testdl4(int x) {
   int i;
   for (i = 1; i < 32; i+=2)
       if ((x & (1<<i)) == 0)
          return 0;
   return 1; 
}

Как бы начать с 1 вместо0 для меня изменить 3-й ответ, данный @ Джонни Йоханссон? (Те же побитовые ограничения)

Answer 5

Похоже, что это тестирование отрицательных чисел, чтобы увидеть, являются ли они и со степенями любых других 2

def testit(x):
   print ( bin(x), test(x))

def test(x):
   for i in range (0, 32, 2):
      if ((x & (1<<i))) == 0:
           print(x, bin(x), bin(1<<i))
           print("{} & {} ({}) is 0".format(x, 1<<i))
           return 0
   print(x, bin(x), ((x & (1<<i))), bin(((x & (1<<i)))))
   return 1

In [494]: testit(-2)                                                                                                                           
-2 -0b10 0b1
-2 & 1 is 0
-0b10 0

In [495]: testit(-3)                                                                                                                           
-3 -0b11 1073741824 0b1000000000000000000000000000000
-0b11 1

In [496]: testit(-4)                                                                                                                           
-4 -0b100 0b1
-4 & 1 is 0
-0b100 0

In [497]: testit(-5)                                                                                                                           
-5 -0b101 0b100
-5 & 4 is 0
-0b101 0

In [498]: testit(-6)                                                                                                                           
-6 -0b110 0b1
-6 & 1 is 0
-0b110 0

In [499]: testit(-7)                                                                                                                           
-7 -0b111 0b100
-7 & 4 is 0
-0b111 0

In [500]: testit(-8)                                                                                                                           
-8 -0b1000 0b1
-8 & 1 is 0
-0b1000 0

In [501]: testit(-9)                                                                                                                           
-9 -0b1001 1073741824 0b1000000000000000000000000000000
-0b1001 1

In [508]: testit(-17)                                                                                                                          
-17 -0b10001 0b10000
-17 & 16 is 0
-0b10001 0

In [515]: testit(-203)                                                                                                                         
-203 -0b11001011 0b1000000
-203 & 64 is 0
-0b11001011 0

Приведенный выше вывод показывает, что все остальные степени двух чисел, которые & с вашим отрицательнымчисло будет 0, если нет, оно прекращает проверку при степенях два из 1073741824. Это помогает?