Найти сколько раз 11₂ число входит в другое используя побитовые операции

#python #алгоритм #python_3x

В задаче просят найти число 11 в другом числе, используя побитовые операции. То есть
ввести в любой системе счисления, программа переведет в двоичный и там посчитает. Пробовал
делать но не вышло даже простое

a = int(input('nam: '))
c = bin(a)
b = len([i for i in c if i == '1'])
print(c)
print(b)

    

Ответы

Ответ 1

Приведите к бинарному виду, вот очень простой пример подсчета, его можно значительно
доработать:

a = input("nam: ")  # например 27
b = bin(a)

print(b)  # '0b11011'

e = 0
check = b[2]
try:
    for num, i in enumerate(b[3:]):
        if i and i == check:
            e += 1
            check = b[num + 1]
        check = i
except IndexError:
    pass

print(e)


Или можно стандартной функцией строк посчитать вхождение подстроки:

b[2:].count('11')


Пример с побитовым сдвигом:

a = int(input("nam: "))  # например 27
e = 1
count = 0
while 1:
    res = a >> e
    if res % 2 == 0:
        count += 1
    e += 1

    if res == 0:
        break
print(count)


Ответ 2

Чтобы определить содержит ли целое число во вводе два подряд идущих бита в двоичном
представлении:

has_adjacent_bits = "11" in bin(int(input()))


Чтобы определить сколько раз входит "11" без перекрытия, можно str.count метод использовать:

>>> "-0b111".count("11")
1


Чтобы найти перекрывающиеся вхождения, см. Подсчёт вхождений перекрывающейся подстроки
в строку:

>>> count_overlapping_substrings("-0b111", "11")
2


Если хочется подсчитать количество смежных пар битов, используя побитовый сдвиг:

def count_overlapping_adjacent_bit_pairs(n):
    count = 0
    n = abs(n)
    while n > 0:
        count += (n & 1) & (n >> 1)
        n >>= 1
    return count


Это считает перекрывающиеся вхождения:

>>> count_overlapping_adjacent_bit_pairs(-0b111)
2


Чтобы посчитать сколько раз 112 входит в число:

def count_adjacent_bit_pairs(n):
    count = 0
    n = abs(n)
    while n > 0:
        if (n & 1) & (n >> 1): # ends with 11
           count += 1
           n >>= 1
        n >>= 1
    return count


Неперекрывающиеся вхождения:

>>> count_adjacent_bit_pairs(-0b111)
1


Вместо n = abs(n) для отрицательных чисел можно возвращать math.inf так как считается
что бесконечное количество единиц слева (2's complement).