Farklı bit sayısı
Görev tanımı
Problem
Negatif olmayan iki tam sayıyı ikili olarak, biri diğerinin üstünde ve sağa hizalı yaz. İkili basamaklarının uyuşmadığı konumları say. Kısa sayının solundaki eksik basamaklar sıfır sayılır.
Örnekler
Input: a = 1, b = 4
Output: 2
Neden: 001 ile 100 ilk ve son konumda uyuşmuyor
Input: a = 7, b = 10
Output: 3
Neden: 0111 ile 1010 sağdan ikinci konum hariç her yerde uyuşmuyor
Input: a = 5, b = 5
Output: 0
Neden: edge case: bir sayı kendisiyle hiçbir zaman uyuşmazlık göstermez
İpuçları
0 / 3
İki sayıyı basamak basamak karşılaştırmak işe yarar, ama tek bir bitwise işlem bütün karşılaştırmaları aynı anda yapabilir.
İki basamak farklıysa tam orada 1, aynıysa 0 üreten bir operatör var. Onu uyguladıktan sonra soru bir sayma sorusuna dönüşür.
İki sayıyı XOR'la, sonra sonuçtaki 1'leri say. Hızlı sayma yolu: değer sıfıra ulaşana kadar değeri kendisinin bir eksiğiyle AND'leyerek en düşük 1'i tekrar tekrar sil ve her seferinde bir sayaca bir ekle.
- Hedef zaman
- O(log max(a, b))
- Hedef alan
- O(1)
Kısıtlar
- a and b are non-negative integers
Çözüm
XOR, girdileri tam olarak uyuşmadığı yerde biti 1 yapar; yani cevap basitçe a XOR b'deki 1'lerin sayısıdır. Onları en düşük 1'i silme tekniğiyle saymak basamak başına değil 1 başına bir döngü turu tutar, çünkü bir çıkarmak en düşük 1'i ve altındaki her şeyi çevirir, AND de o 1'i siler. Bu yüzden döngü cevap kadar döner. Zaman O(farklı bit sayısı), en fazla O(log(büyük girdi)); alan O(1).
def differing_bits(a, b):
x = a ^ b # a 1 wherever the two numbers disagree
count = 0
while x:
x &= x - 1 # clear the lowest remaining 1
count += 1
return count
print(differing_bits(1, 4)) # -> 2
print(differing_bits(7, 10)) # -> 3
print(differing_bits(5, 5)) # -> 0Kodda değil de fikirde mi takıldın? 1 olan bitleri saymak bunu anlatıyor.