Dördün kuvveti kontrolü
Görev tanımı
Problem
İşaretli 32 bit bir tam sayıya sığan bir n tam sayısı verildiğinde, n 4'ün bir tam sayı kuvvetine (1, 4, 16, 64 ve devamı) eşitse True, değilse False döndür. Sıfır ve negatif sayılar asla dördün kuvveti değildir. Döngü olmadan, yalnız bit işlemleriyle cevap vermeye çalış.
Örnekler
Input: n = 16
Output: True
Neden: 16, 4'ün karesi
Input: n = 8
Output: False
Neden: 8 ikinin kuvveti ama tek 1 olan biti yanlış yerde
Input: n = 1
Output: True
Neden: edge case: 4'ün 0. kuvveti 1
İpuçları
0 / 3
Dördün her kuvveti aynı zamanda ikinin kuvvetidir. İkinin bir kuvvetinin ikili olarak nasıl göründüğünü hatırlayarak başla.
İkinin bir kuvvetinin tam olarak bir tane 1 olan biti vardır ve n & (n - 1) onu siler. 1, 4, 16 ve 64 için o bitin durduğu yerle ilgili başka ne doğru?
Dördün bir kuvvetinin tek biti her zaman çift bir konuma düşer: 0, 2, 4 ve devamı. n'in pozitif olduğunu, tek bir 1 olan biti olduğunu ve her çift konumunda 1 olan bir maskenin o biti koruduğunu kontrol et.
- Hedef zaman
- O(1)
- Hedef alan
- O(1)
Kısıtlar
- n fits in a signed 32-bit integer
Çözüm
Dördün bir kuvveti, tek 1 olan biti çift bir konumda duran ikinin bir kuvvetidir, çünkü dörtle her çarpma o biti iki basamak sola kaydırır. İkinin bir kuvvetinden bir çıkarmak onun tek bitini ve altındaki her biti çevirir; bu yüzden n & (n - 1) tam olarak ikinin kuvvetleri için sıfırdır. 0x55555555 maskesinin 32 bitlik bir kelimenin her çift konumunda 1'i vardır; yani 1, 4, 16 ve 64'ün bitini korur ama 2, 8 ve 32'nin bitini düşürür. Zaman ve alan O(1).
def is_power_of_four(n):
one_bit = n > 0 and (n & (n - 1)) == 0 # a power of two has a single set bit
return one_bit and (n & 0x55555555) != 0 # ...and for four it sits at an even position
print(is_power_of_four(16)) # -> True
print(is_power_of_four(8)) # -> False
print(is_power_of_four(1)) # -> True
print(is_power_of_four(0)) # -> FalseKodda değil de fikirde mi takıldın? Maskeler ve ikinin kuvveti bunu anlatıyor.