Конкурентное кодирование - биты маски - десятичные в двоичные - PullRequest
Новая
       31

Конкурентное кодирование - биты маски - десятичные в двоичные

0 голосов
/ 07 октября 2018

Я пытаюсь решить проблему конкурентного кодирования.Мне удалось пройти все тестовые случаи, кроме одного.Я предполагаю, что я пропустил какой-то случай с краем.

Проблема:

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

Вот мой код: 

import math
for _ in range(int(input())):
    n = int(input()) #The given number
    a = list(map(int, input().split())) #Positions at which the bits need to be masked
    b = str(bin(n))[:1:-1]
    for i in a:
        if i<=len(b) and b[i-1]=='1':
            n-=math.pow(2, i-1)
    print(int(n))

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

1 Ответ

0 голосов
/ 07 октября 2018

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

for _ in range(int(input())):
    # The given number
    n = int(input())
    # Create the bit mask
    mask = sum(1 << int(u) for u in input().split()) >> 1
    # Invert the bits in n which are also in mask
    n ^= n & mask
    print(n)
...