3590 - Bit Distance

Cerință

Se dă un număr natural n. Considerând reprezentarea in baza 2 a acestui număr, calculați distanța dintre primul bit setat și ultimul bit setat. Distanța dintre 2 biți este egală cu numărul de biți aflați intre biții respectivi.

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." Programul va afișa pe ecran distanța dintre primul și ultimul bit setat al numărului citit. În caz contrar, se va afișa pe ecran: "Datele de intrare nu corespund restricțiilor impuse."

Restricții de precizări

• 1 ⩽ n ⩽ 2^64

Exemplul 1

Intrare

82

Ieșire

Datele introduse corespund restricțiilor impuse.

6

Exemplul 2

Intrare

4

Ieșire

Datele introduse corespund restricțiilor impuse.

1

Rezolvare ver. 1

<syntaxhighlight lang="python" line="1" start="1"> def validare(n):

   return n.isdigit() and 1 <= int(n) <= pow(2, 64)

def bit_distance(n):

   # Teoretic, primul bit este întotdeauna 1. Dacă mutăm toți biții la dreapta până când rămâne numărul 0b000001,
   # vom afla distanța cerută.
   distanta = 1

   if n == 0:
       distanta = 0
   else:
       # Întâi, mutăm biții la dreapta până când vom avea un 1 la final
       while not (n & 0b001):
           n >>= 1
       # Acum, mutăm biții la dreapta până când rămâne numărul 1, adică până când ajungem la primul bit setat
       while n != 1:
           n >>= 1
           distanta += 1
   return distanta

if __name__ == "__main__":

   n = input("Introduceti n: ")
   if validare(n):
       n = int(n)
       # Se afișează distanța calculată
       print("Datele introduse corespund restricțiilor impuse.")
       print("Distanța cerută este:", bit_distance(n))

   else:
       print("Datele introduse nu corespund restricțiilor impuse.")

</syntaxhighlight>