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

<syntaxhighlight lang="python" line="1" start="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.")

</syntaxhighlight>