Binary to Decimal

Q: İkilikten ondalığa dönüştürmenin zaman karmaşıklığı nedir?

Her iki döngü de n karakterin her birini bir kez ziyaret eder, bu nedenle O(n) zaman alır. Yalnızca bir veya iki sayı tutarlar; bu da O(1) ek alan demektir. 31 karakterlik bir dize için bu, 31 adımdır.

Q: Bit kaydırmalarıyla ikilik sistemi onluk sisteme dönüştürebilir misin?

Evet. value << 1 değeri iki katına çıkarır ve | digit en düşük biti ayarlar; bu nedenle value = (value << 1) | digit , value * 2 + digit ile aynı işi yapar. Kaydırma biçimi bitleri taşıdığınızı açıkça gösterirken, aritmetik biçim 2 dışındaki tabanlarda da çalışır.

BaşlangıçMatematik ve simülasyon Bit işlemleri

+10

Yalnızca 0 ve 1 karakterlerini kullanarak negatif olmayan bir sayıyı ikili olarak ifade eden bir s dizgesi alırsın. Bu sayının değerini normal bir tam sayı olarak döndür. Sıfır sayısı tek karakterli 0 olması dışında, dizgenin başında sıfır bulunmaz.

Fonksiyon

toDecimal(s: string) → integer

sstring: sayının ikili basamakları
Döndürürinteger: s'nin tamsayı olarak değeri

Kısıtlar

1 ≤ s.length ≤ 31
s yalnızca 0 ve 1 içerir.
s, s "0" olmadığı sürece 1 ile başlar.
Yerleşik bir taban dönüştürme işlevini çağırmak yerine basamakları kendiniz okuyun.

Örnekler

Girdi: s = "1101"
Çıktı: 13
Açıklama: Sağdan başlayarak basamakların değerleri 1, 2, 4 ve 8'dir. 1101 sayısında 8, 4 ve 1 değerli basamaklarda 1 vardır ve 8 + 4 + 1 = 13.

Girdi: s = "0"
Çıktı: 0
Açıklama: Tek bir 0 içinde hiçbir basamakta 1 bulunmadığından, değeri 0 olur.

Girdi: s = "10000000"
Çıktı: 128
Açıklama: Tek 1'in sağında yedi 0 vardır, bu yüzden 2^7 = 128 değerindeki basamakta yer alır.

Gönderirken +16 gizli test

Ek soru

2'den 16'ya kadar herhangi bir tabanda yazılmış bir sayıyı, a ile f harflerinin 10'dan 15'e kadar olan rakamları temsil ettiği aynı döngüyle okuyabilir misin?

İpuçları

Tek tek açın. Her biri biraz daha fazlasını gösterir.

3 ipucundan 0 açıldı

Çözüm

Her ikili basamak, sağ uçtan ne kadar uzakta olduğuna bağlı olarak bir ikinin kuvvetini temsil eder. Bu kuvvetleri sağdan başlayarak toplayabilir ya da diziyi soldan okuyup her adımda değeri ikiyle çarpabilirsiniz. İkiye katlama döngüsü hiçbir kuvvet hesaplamaz ve 10 yerine 2 kullanılması dışında ondalık metni okumak için kullandığınız döngünün aynısıdır.

Basamak değerlerini sağdan ekleyin

Sezgi

En sağdaki basamak 1 değerindedir; bir sonraki 2, ardından 4, 8 olur ve sola doğru her adımda iki katına çıkar. Sayı, basamak değerleri 1 olan konumların değerlerinin toplamıdır. Bu yüzden son karakterden ilk karaktere doğru ilerleyin, geçerli basamak değerini power içinde tutun ve basamak 1 olduğunda bu değeri toplama ekleyin.

1101 için 1 ile karşılaşırsınız (1 ekleyin), 0 (2'yi atlayın), 1 (4 ekleyin) ve 1 (8 ekleyin); toplam 13 olur. Her basamak bir kez ziyaret edilir, bu nedenle döngü O(n) zaman ve iki sayı kadar bellek kullanır.

power değerinin büyüklüğüne dikkat edin. 31 basamaklı bir dize için son basamakta 2^30 değerine ulaşır ve ardından bir kez daha iki katına çıkarak 2^31 olur; bu değer işaretli 32 bitlik bir tam sayıya sığmaz. power değerini 64 bitlik bir değişkende tutun veya son basamaktan sonra ikiye katlamayı bırakın.

Algoritma

total = 0 ve power = 1 olarak ayarla.
Dizgede son karakterden ilk karaktere doğru ilerle.
Karakter 1 ise power değerini total değerine ekle.
Bir basamak sola geçmeden önce power değerini ikiye katla.
total değerini döndür.

def toDecimal(s):
    total = 0
    power = 1  # the place value of the rightmost digit
    for i in range(len(s) - 1, -1, -1):
        if s[i] == "1":
            total += power
        power *= 2
    return total

Soldan ikiye katla ve ekle

Sezgi

Dizgeyi soldan okuyun ve şimdiye kadar okunan rakamların gösterdiği sayıyı tutan value değerini koruyun. Bir ikili rakam daha eklemek, önceki her rakamı bir basamak sola kaydırır; böylece değerleri iki katına çıkar ve ardından yeni rakamı ekler. Bu nedenle her adım value = value * 2 + digit şeklindedir.

1101 için value önce 1 olur, ardından 1 * 2 + 1 = 3, sonra 3 * 2 + 0 = 6 ve son olarak 6 * 2 + 1 = 13 olur. Dizgenin her öneki daha küçük bir ikili sayıdır ve döngü tam olarak bu sayıyı tutar; bu nedenle son rakamdan sonra sayının tamamını içerir.

Değer hiçbir zaman nihai yanıtı aşmaz; bu nedenle 31 basamaklı bir dizge için 2^31-1 sınırları içinde kalır ve 32 bitlik bir tam sayı yeterlidir. Rakam, karakter kodundan '0' karakterinin kodunun çıkarılmasıyla elde edilir; böylece '1' 1'e, '0' ise 0'a dönüşür. Bu, herhangi bir tabandaki bir sayıyı metinden ayrıştırmanın standart yoludur.

Algoritma

value = 0 olarak ayarla.
Soldan sağa her karakter için, '0' karakterinin kodunu çıkararak onu bir rakama dönüştür.
value = value * 2 + digit olarak ayarla.
value değerini döndür.

def toDecimal(s):
    value = 0
    for ch in s:
        # Shift the digits read so far one place left, then add the new one.
        value = value * 2 + (ord(ch) - ord("0"))
    return value

Tuzaklar ve uç durumlar

Yanlış yanıtların çoğu, gezinme yönünden veya basamağın türünden kaynaklanır.

En soldaki basamağa 1 basamak değerini vermek. Basamak değerleri sağdan başlar; bu nedenle son karakterden başlayarak ilerleyin veya soldan başlayan iki katına çıkarma döngüsünü kullanın.
Basamak yerine karakteri eklemek. Birçok dilde '1' sayısı 49'dur; bu nedenle value * 2 + '1' çok büyük bir değer verir. Önce '0' değerini çıkarın.
Basamak değerinin taşmasına neden olmak. 31. basamaktan sonra power değerini iki katına çıkarmak, 32 bitlik bir tamsayıda 2^31 değerinin taşmasına veya programın çökmesine neden olur.
Her basamak değerini kayan noktalı sayı kuvvet fonksiyonuyla hesaplamak. C, C++ ve Java'da pow(2, k) bir double döndürür ve sonucun yeniden tamsayıya dönüştürülmesi gerekir.

Sıkça sorulan sorular4

İkilik sayı onluk sayıya nasıl dönüştürülür?

Her basamağa bir basamak değeri verin: en sağdaki için 1, ardından sola doğru 2, 4, 8 ve böyle devam edin. 1 olan basamakların basamak değerlerini toplayın. 1101 için bu, 8 + 4 + 1 = 13 eder.

Değeri iki katına çıkarmak neden işe yarıyor?

İkili bir sayının sonuna bir basamak daha yazmak, önceki tüm basamakları bir basamak sola kaydırır ve her basamağın değeri sağındaki basamağın iki katıdır. Böylece eski değer iki katına çıkar ve yeni basamak 0 veya 1 ekler. Bu işlemi ilk basamaktan son basamağa kadar tekrarlamak sayının tamamını oluşturur.

İkilikten ondalığa dönüştürmenin zaman karmaşıklığı nedir?

Her iki döngü de n karakterin her birini bir kez ziyaret eder, bu nedenle O(n) zaman alır. Yalnızca bir veya iki sayı tutarlar; bu da O(1) ek alan demektir. 31 karakterlik bir dize için bu, 31 adımdır.

Bit kaydırmalarıyla ikilik sistemi onluk sisteme dönüştürebilir misin?

Evet. value << 1 değeri iki katına çıkarır ve | digit en düşük biti ayarlar; bu nedenle value = (value << 1) | digit, value * 2 + digit ile aynı işi yapar. Kaydırma biçimi bitleri taşıdığınızı açıkça gösterirken, aritmetik biçim 2 dışındaki tabanlarda da çalışır.

Python

def toDecimal(s):
    # Kodu buraya yazın

Test durumları

Durum 1

Durum 2

Durum 3

Girdi

s = "1101"

Beklenen