Bit sırasını ters çevir
Görev tanımı
Problem
Negatif olmayan bir tam sayıyı, solu sıfırlarla doldurulmuş 32 ikili basamaklık sabit bir alan olarak düşün. Bu 32 basamağın sırasını ters çevirince elde ettiğin değeri döndür; en düşük basamak en yüksek olsun, en yüksek de en düşük. Girdinin büyüklüğü ne olursa olsun genişlik her zaman 32.
Örnekler
Input: value = 1
Output: 2147483648
Neden: tek düşük basamak alanın en tepesine kadar gider
Input: value = 3
Output: 3221225472
Neden: iki düşük basamak en yüksek iki basamak olur
Input: value = 0
Output: 0
Neden: edge case: sıfırlardan oluşan alan iki yönde de aynı okunur
İpuçları
0 / 3
Sayıyı metne çevirmek, metni ters çevirmek ve geri okumak işe yarar, ama buradaki bütün mesele bunu sayının kendisi üzerinde aritmetikle yapmak.
Cevabı basamak basamak kur. Girdiyi en düşük basamağından yukarı doğru okumak, cevabın basamaklarının eklenmesi gereken sırayı tam olarak verir.
32 kez tekrarla: sonucu bir basamak yukarı kaydırarak yer aç, girdinin en düşük basamağını bu yere kopyala, sonra girdiyi bir basamak aşağı kaydır. Alan genişliğini sabitleyen şey tam 32 tur olması.
- Hedef zaman
- O(1)
- Hedef alan
- O(1)
Kısıtlar
- value is a non-negative integer read as 32 bits
Çözüm
Girdiyi aşağıdan yukarı okuyup sonucu da aşağıdan yukarı yazmak ters çevirmeyi bedavaya üretir, çünkü ilk okunan basamak sonraki kaydırmalarla en sola itilir. Her tur sonucu yukarı kaydırarak bir yer açar, girdinin en düşük basamağını bir maske ve OR ile oraya kopyalar, sonra o basamağı girdiden atar. Küçük bir sayının erken durmak yerine tam alan genişliğine doldurulmasını, tam 32 tur çalıştırmak sağlar. Zaman O(32), yani sabit; alan O(1).
def reverse_bits(value):
result = 0
for _ in range(32): # a fixed width, whatever the input size
result = (result << 1) | (value & 1) # open a slot, copy the low digit
value >>= 1 # drop the digit just consumed
return result
print(reverse_bits(1)) # -> 2147483648
print(reverse_bits(3)) # -> 3221225472
print(reverse_bits(0)) # -> 0Kodda değil de fikirde mi takıldın? İkili sayılar ve bit seviyesinde işlemler bunu anlatıyor.