3956 - Erase Bits

Cerință

Dându-se un număr natural n, să se afle toate numerele obținute resetând succesiv cel mai nesemnificativ bit cu valoarea 1, fără a folosi variabile auxiliare.

Date de intrare

Programul citește de la tastatură numărul n.

Date de ieșire

Dacă datele sunt introduse corect, pe ecran se va afișa: "Datele de intrare corespund restricțiilor impuse." și programul va afișa pe ecran numerele. În caz contrar, se va afișa pe ecran: "Datele de intrare nu corespund restricțiilor impuse."

Restricții de precizări

• 1 ⩽ n ⩽ 10^18

Exemplul 1

Intrare

123

Ieșire

Datele introduse corespund restricțiilor impuse.

122 121 119 111 95 63 0

Exemplul 2

Intrare

86

Ieșire

Datele introduse corespund restricțiilor impuse.

85 83 79 63 0

Rezolvare ver. 1

def validare(n):
    return str(n).isdigit() and 1 <= int(n) <= 10**18

def resetare_bit(n):
    while n > 0: # Cât timp n este mai mare ca și 0
        print(n - 1, end=" ") # Afișăm numărul obținut prin scăderea cu 1
        n &= n - 1 #  Resetăm cel mai nesemnificativ bit cu valoarea 1
    print(0)  # Afișăm și 0 la final

if __name__ == "__main__":
    # Citirea valorii pentru n de la tastatură
    n = input("Introduceți numărul n: ")
    if validare(n):
        n = int(n)
        print("Datele introduse corespund restricțiilor impuse.")
        resetare_bit(n)
    else:
        print("Datele introduse nu corespund restricțiilor impuse.")