CP #37: Bit Manipluation Problemleri
1. Decode XORed Array
Problem surada.
Cozum
XOR operatoru, iki binary sayi arasindaki bit farklarini ortaya cikartiyor. Yani XOR sonucu 1 gelmisse, iki taraftaki bit farkli, 0 gelmisse ayni demektir. Bu durumda XOR sonucuna bakarak, ve de encode edilmemis arrayin ilk elemani elimizde olduguna gore, ikinci elemanini reverse XOR ile bulabiliriz.
Soyle:
encoded[i] = arr[i] ^ arr[i+1]
olduguna gore, encode edilmemis arrayin ilk elemanina first dersek,
encoded[1] = first ^ arr[i+1]
Bu denklemde sol tarafi biliyoruz, ve de first degerini biliyoruz. O zaman geriye kalan basit bir cebir islemine benzer sekilde arr[i+1] bilinmeyenini esitligin bir tarafinda birakmak.
arr[i+1] = ???
HINT 1: XOR islemi siralamadan bagimsizdir. Toplama islemi gibi. Ne de olsa iki sayi arasindaki bit farklarina bakiyoruz, ilk once hangisinin geldiginin bir onemi yok.
HINT 2:
a = b ^ c ise;
a = b ^ c ise;
b = a ^ c ve de c = b ^ a
seklinde degiskenler yer degistirilebilir. Bu su demek, XOR operatorunun tersi yine XOR'dur. a sayisi ile b sayisi XOR sonucu c veriyor ise, a'yi c ile XOR yaparak, b'yi geri elde edebiliriz. Yukaridaki sorunun cevai su sekilde oluyor:
arr[i+1] = arr[i] ^ encoded[i]
O zaman implementasyon cok kolay bir hale geliyor:
def decode(self, encoded: List[int], first: int) -> List[int]:
# encode edilmemis arrayin ilk elemani bize first argumani ile geliyor
arr = [first]
for i in range(len(encoded)):
cur = arr[i] ^ encoded[i]
arr.append(cur)
return arr
O(n) time compl. ve O(n) space comp. sahip gayet basit bir cozum elde ettik.
2. Number of Steps to Reduce a Number to Zero
Problem surada.
Cozum
Kisaca ozetlersek, verilen sayi cift ise ikiye bolecegiz, tek ise 1 cikartacagiz ve sifira ulasana kadar devam edecegiz. Bu problem icin bit manipluasyon sart degil aslinda ama bizim konumuz bu oldugu icin bu sekilde bir cozume gidelim.
def numberOfSteps(self, num: int) -> int:
steps = 0
# sayi sifir olana kadar devam edelim
while num:
# sayi cift ise
if num & 1 == 0:
# saga dogru 1 bit kaydirirsak, 2'ye bolmus oluruz
num >>= 1
else:
# bir sayiyi 1 ile XOR yapmak, sondaki biti 1 ise 0 yapacagindan
# sayidan 1 cikartmis gibi olur
num ^= 1
steps += 1
return steps
3. XOR Operation in an Array
Problem surada.
Cozum
Gayet straightforward bir problem. Direk implementasyona gecebiliriz:
def xorOperation(self, n: int, start: int) -> int:
nums = [start + 2 * i for i in range(n)]
ret = nums[0]
for i in range(1, len(nums)):
ret ^= nums[i]
return ret
Bu hali ile leetcode'a submit ettigimde 32ms ile, gonderilerin %54'unden daha hizli oldugunu gordum. Burada neyi iyilestirebiliriz?
Once nums arrayini olusuturp sonra XOR islemini yapiyoruz. Bu iki islem de aslinda ayni array uzerinde oldugundan, birlestirilebilir. Ayrica, 2 ile carpma islemini de sola 1 bit kaydirarak daha performansli bir sekilde yapabiliriz.
def xorOperation(self, n: int, start: int) -> int:
ret = start
for i in range(1, n):
ret ^= start + (i << 1)
return ret
Bu hali ile 20ms suruyor ve gonderilerin %98'inden daha hizli.
4. Convert Binary Number in a Linked List to Integer
Problem surada.
Cozum
Ilk etapta, verilen binary temsil, ilk once en buyuk basamak ile basladigi icin, ve de verilen sayinin kac basamakli oldugunu bilmedigimiz icin, once tum basamak degerlerini bir array icerisinde biriktirip sonra int'e cevirmek cazip bir fikir gibi gozuktu.
Yani olay su, verilen linked list ege 1, 0, 0 ise, en bastaki bir aslinda 2^2' yi temsil ediyor demektir. Ancak biz linked listi traverse ederken o anda, linked list icerisinde kac node bulundugunu bilmedigimiz icin hangi basamakla muhattap oldugumuzu bilmuyoruz.
Bu acidan yazdigim naive implementasyon su sekilde idi:
def getDecimalValue(self, head: ListNode) -> int:
# once tum basamaklari array icerisinde biriktirelim
digits = []
cur = head
while cur:
digits.append(cur.val)
cur = cur.next
# daha sonra bunlari sondan baslayarak int'e cevirelim.
# sonran basliyoruz cunku orasi least significant basamak.
ret = 0
pw = 1 # basamak degeri, 2^0, 2^1, 2^2 ... seklinde devam ediyor
for i in range(len(digits) - 1, -1, -1):
ret += pw * digits[i]
# her adimda pw'yi 2 ile carpip yeni basamak degerini elde ediyoruz
pw *= 2
return ret
Evet cozumi veriyor ama cok teferruatli. Buradaki basamak degerini bilmeme problemi aslinda 10'luk sistemdeki linked list sorularinda da karsimiza cikiyor. Ornegin bir linked list ile soyle ifade edilen sayiyi int'e ceviriniz:
8 -> 5 -> 6 -> 4
Sonucta geriye 8bin 5yu altmis dort dondurmemiz gerek. Ama linked listi traverse ederken 8'i gordumuzde bunun binler basamagi oldugunu bilmuyoruz.
Burada soyle bir trick var. 8'i ilk gordugumuzde, bunu 1'ler basamagi gibi kabul edebiliriz. Daha sonra 5'e gectigimizde ise anliyoruz ki bir basamak daha varmis. Demek ki onceki hesapladigimiz degeri 10 ile carpmamiz ve yeni gelen basamagi buna eklememiz gerek. Her adimda bunu yaparsak, sonunda istenen degeri elde edebiliriz.
Ayni taktigi binary sayi icin de uygularsak iki tane dongu kullanmamiza gerek kalmiyor:
def getDecimalValue(self, head: ListNode) -> int:
ret = 0
while head:
# aslinda olan su:
# ret = ret * 2 + cur.val
# ancak cur.val degeri 0 ya da 1 olabilecegi icin
# toplama islemi icin OR kullanabiliriz
# 2 ile capma icin de sola 1 bit kaydirmamiz yeterli
ret = (ret << 1) | head.val
head= head.next
return ret
5. Sum of Digits in Base K
Problem surada.
Cozum
Problem cok straightforward ve cok kolay ancak, 10 base ile verilen bir sayiyi baska bir base'e cevirme isimize yarayacak bir egzersiz olabilir.
def sumBase(self, n: int, k: int) -> int:
# 10luk tabanca verilen n sayisini k tabanina cevirirken
# her bir digit'i bir arrayda tutuyoruz
digits = []
while n:
digits.append(n % k)
n // = k
return sum(digits)
O(n) time comp ve O(n) space comp. elde ettik. Belki bir kucuk iyilestirme ile O(1) space'e indirgeyebiliriz. Cunku her bir digiti arrayde tutuyoruz ama sonuc olarak arraydaki tum elemanlari toplayip geri donduruyoruz.
def sumBase(self, n: int, k: int) -> int:
ret = 0
while n:
ret += n % k
n // = k
return ret
Bundan da iyisi artik samda kayisi.
6. Hamming Distance
Problem surada.
Cozum
Tanima baktigimizda zaten goruyoruz ki, ilk adim olarak verilen iki sayinin bitleri arasinda hangileri farkli hangileri ayni. XOR operatoru ile farkli olan bitleri bulabiliyoruz. Geriye kalan, XOR islemi sonucu ortaya cikan sayida kac tane 1 biti oldugunu bulmak.
def hammingDistance(self, x: int, y: int) -> int:
# iki sayi arasindaki bit farklari
z = x ^ y
# z icerisinde kac tane 1 bit var?
# en sondaki basamaga bakarak baslayabiliriz
# eger 1 ise, ret degerini 1 artiracagiz
# daha sonra saga dogru 1 bit kaydira kaydira sayiyi sifirlayacagiz
ret = 0
while z:
# eger son bit 1 ise, ret degerini 1 artiracagiz:
# if z & 1:
# ret += 1
# bunun yerine direkman AND operatorunden gelen degeri ekleyebiliriz
ret += z & 1
# son basamagi kontrol ettik.
# simdi sola dogru ilerlemek icin z'yi bir bit saga kaydiriyoruz.
z >>= 1
return ret
Verilen sayinin kac bitlik olduguna bagli olarak degisen bir time compl. sahibiz. Ornegin, sayilar 64 bit ise, sonucta while loop'u en fazla 64 kere donecektir. Bu durumda O(1) time ve O(1) space compl. sahip bir cozum elde etmis oluyoruz.
7. Sort Integers by The Number of 1 Bits
Problem surada.
Cozum
Bu da cok straightforward bir problem olmakla beraber, hatta cok kucuk bir kismi bit manipluation ile alakali olmasina ragmen, custom sorting icerdigi icin kiymetli bana gore.
Yapmamiz gereken acik ve net. Arraydaki her bir sayinin kac tane 1 bit icerdigini bulacagiz. Daha sonra arrayi bu bit sayilarina gore siralayacagiz. Eger iki sayi arasinda 1 bit sayisi esit ise, sayilarin kendi degerlerine gore siralayacagiz.
Degeri 1 olan bitlerin sayisini bulmak kolay. Peki bu siralamayi nasil yapacagiz? Aklima ilk gelen yontem, custom bir compare fonk. yazmak ve bunu ile sort etmek. Python3'te bu is biraz merasime donusmus, o yuzden functools kutuphanesi ile bir ek adim atmak gerekiyor.
import functools
def sortByBits(self, arr: List[int]) -> List[int]:
def one_bits(num):
return bin(num).count("1")
def compare(x, y):
# verilen iki sayi icin 1-bit sayilarini hesaplayalim
n1 = one_bits(x)
n2 = one_bits(y)
# eger 1-bit sayilari esit ise
# sayilarin kendisini kiyaslamak gerek
# compare fonk. birinci arguman kucuk ise -1 (ya da negatif bir deger),
# argumanlar esit ise 0, ve ikincisi buyuk ise de +1 (ya da pozitif bir deger)
# dondurmesi gerekiyor.
# en kolay yolu verilen birinci elemandan, ikinciyi cikarmak.
if x == y:
return x - y
else:
return n1 - n2
# custom compare fonk. ile verilen arrayi sort ediyoruz
return arr.sort(key=functools.cmp_to_key(compare))
Ancak burada bir trick var. Eger elimizde array olarak tuple degerleri var ise, python sort metodu cok akillica davranarak, tum elemanlari tuple icerisindeki 1. elemanlara gore siraliyor. Esitlik olmasi durumunda, tuple icerisindeki 2. elemana gore siraliyor. Yani bizim aslinda yukarida yaptigimiz custom sorting (bit_sayisi, sayinin_kendisi) seklinde tuple'lardan olusan bir array icin default sort metodu ile elde edebilirdik.
Bir ornek vermek gerekirse, [(0, 3), (1, 4), (0, 1), (1, 2)] seklinde bir tuple arrayini sort edersek, iki elemana gore de sort edildigini gorecegiz: [(0, 1), (0,3), (1, 2), (1, 4)] seklinde. Mukemmel bir ozellik.
Bu trick ile implementasyon bayagi guzellesiyor, kisaliyor:
def sortByBits(self, arr: List[int]) -> List[int]:
# arr icerisindeki elemanlardan 1-bit sayisi
#ve sayinin kendisini barindiracak sekilde tuple'lar olusturuyoruz
arr2 = [(bin(k).count("1"), k) for k in arr]
# sayilarin kendilerini sorted olarak donduruyoruz
return [p[1] for p in sorted(arr2)]
Bacak olursak, O(n) ile iki iterasyon yaptik. Ekstra O(n) de ekstra space kullandik.
8. Single Number
Problem surada.
Cozum
Bircok farkli yontemle cozulebilecek bir soru ama biz yine bitwise takilalim. Bir sayiyi kendisi ile XOR islemina sokarsak, sifir elde edecegimiz asikar. Ne de olsa kendisi ile farkli bir biti olamaz. Bu durumda eger array icerisinde tum sayilar 2ser kere yer alsa idi, tum arrayi XOR'ladigimizda sifir elde edecektik.
Bununla beraber, bir sayiyi sifir ile XOR islemine sokmak da sayinin kendisini verecektir. Cunku sayinin sifirdan farkli bitleri sifir ile XOR islemine girecek ve 1 uretecekti. Bu da sayinin orjinal haline denk oluyor.
Demek ki, tum arrayi XOR islemine soktugumuzda, iki kere gecen elemanlar kendilerini sifirliyor. Sona kalan 1 kez tekrar eden sayi da sifir ile XOR'a girdigi zaman sonuc olarak kendisini veriyor. Cok uzattik, 1 kere tekrar eden eleman, tum arrayin XOR'lanmasi ile bulunabilir.
def singleNumber(self, nums: List[int]) -> int:
ret = nums[0]
for i in range(1, len(nums)):
ret ^= nums[i]
return ret
O(n) time compl. ve O(1) space compl. ile guzel bir cozum denilebilir.
9. Number Complement
Problem surada.
Cozum
Verilen sayi icerisindeki tum bitleri flip etmemiz gerekli. Bu da demek oluyor ki, sifir olan bitler 1 olacak, 1 olanlar ise sifir olacak. Bunu nasil yapabiliriz? Bir biti 1 ile XOR islemine sokarsak, istedigimiz sonucu elde edebilecegimizi goruyoruz. Cunku bit zaten 1 ise, 1 ile XOR'landiginda 0 dondurecek. Tersi icin ise 1 dondurecektir.
Peki her bir biti nasil 1 ile XOR islemine sokacagiz? Sondan baslayarak, basamak basamak ilerleyebiliriz. Her bir adimda, 1'i sola kaydirarak.
def findComplement(self, num: int) -> int:
# oncelikle sayinin kac bitten olsutugunu bulmamiz gerek
# daha once bahsetmistik, python integer degerlerini
# arbitrary bitler ile tutuyor. yani sabit bir bit sayisi yok.
for i in range(num.bit_length()):
# birinci basamaktan baslayarak, her bir basamagi 1 ile xor'a sokuyoruz.
num = num ^ (1 << i)
return num
10. Prime Number of Set Bits in Binary Representation
Problem surada.
Cozum
Aslinda bu problemi atlayacaktim ama cakal bir yon farkettim. Ilk aklima gelen naive yontemde, verilen sayi araliklarindaki tum sayilarin 1-bit sayiarini bulmak ve her biri icin asal olup olmadiklarina bakmakti. 1-bit sayisini bulmak kolay, binary temsil icerisinde toplam kac adet 1 olduguna bakacagiz. Ama bir sayinin asal olup olmadigini anlamak biraz daha amelece.
Yalniz burada kisitlamalara bakarsak, 1. maddede su yaziyor:
1. left, right will be integers left <= right in the range [1, 10^6].
Yani rakamlar en fazla 1 milyona kadar gidebilir. Diyelim ki 1 milyon, kac adet bit icerebilir en fazla?
2^19 = 524288 ve
2^20 = 1048576
oldugunu goruyoruz. Demek ki en fazla 20 bit icerebilir. Bu durumda, bir sayinin 1 bit sayisi toplami da en fazla 20 olabilir demek. Demek ki asal olup olmadigina bakmak icin, onceden ayarlanmis bir set kullanabiliriz, cunku 0'dan 20'ye kadar olan asal sayilar cok degil.
def countPrimeSetBits(self, left: int, right: int) -> int:
ret = 0
# 0'dan 20'ye kadar olan asay sayilar
primes = {2, 3, 5, 7, 11, 13, 17, 19}
for num in range(left, right+1):
ones = bin(num).count("1")
if ones in primes:
ret += 1
return ret
Bu sayede O(n) time compl. ve O(1) space compl. ile problemi cozmus olduk. Cikaracagimiz ders, problemde verilen kisitlamalar kullanilarak cakal optimizasyonlar yapilabilir. Biz burada en genel anlamda verilen bir sayinin asal olup olmadigini bulan bir fonk. yazsaydik, sonucta elde edilecek time compl. cok daha yuksek olacakti.
Ozet
Cok kisaca ogrendigimiz bilgi parcaciklarini toparlayalim:
1. XOR sirasi farketmez
a ^ b = b ^ a
operatorler esitligin diger tarafina atilabilir
a = b ^ c ise
b = a ^ c ve
c = b ^ a
yani XOR'un tersi gene XOR dur.
Bir sayiyi SIFIR ile XOR islemine sokmak, kendisini verir.
x ^ 0 = x
2. Basamaklari Linked-list ile ifade edilen sayiyi, int'e cevirme:
Once tum basamaklari toplayip sonra tersten gitmeye gerek yok.
Her bir yeri basamak geldiginde, oncekini 2 ile (binary ise), ya da 10 ile (decimal ise)
carparak ilerlersek tek pass ile int'e cevirebiliriz.
3. Custom compare ile sort etme:
python3 ile birlikte cmp_to_key kullanmak gerekiyor.
import functools
def compare(x, y):
return x - y
list.sorted(key=functools.cmp_to_key(compare))
4. sorted default davranis ise, verilen tuple'lari once 1. elemana gore
esitlik durumunda ise diger elemana gore sort ediyor.
sorted([(0, 3), (1, 4), (0, 1), (1, 2)] ) --> [(0, 1), (0, 3), (1, 2), (1, 4)]
5. sorted(list) vs list.sort:
list.sort inplace olarak sort eder ve biraz daha performasnlidir.
sorted(list) ise yeni bir liste olusturur.
6. num.bit_length()
ile verilen integer icerisinde kac bit oldugu alinabilir.
Baska problemlerde gorusmek uzere.
Stay hungry, stay foolish, stay healthy :)
Yorumlar
Yorum Gönder