Decimal to Binary

Q: Division yerine bit işlemleri kullanarak ikili sisteme dönüştürebilir misin?

Evet. n & 1 en düşük biti verir ve n >> 1 bu biti atar; bu, negatif olmayan sayılar için n % 2 ve n / 2 ile aynıdır. Döngü ve ters çevirme aynı kalır. Bölmeyi açıklamak daha kolaydır; kaydırma sürümü ise düşük seviyeli kodlarda yaygındır.

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

+10

Negatif olmayan bir tamsayı n verilir. Bu sayının başında sıfır olmayan 0 ve 1 rakamlarından oluşan ikili gösterimini bir dize olarak döndürün. Yanıtı 0 ile başlayan tek sayı sıfırın kendisidir; bu sayı "0" olarak yazılır.

Fonksiyon

toBinary(n: integer) → string

ninteger: dönüştürülecek sayı
Döndürürstring: n'nin ikili basamakları bir dize olarak

Kısıtlar

0 ≤ n ≤ 2³¹-1
Yerleşik bir taban dönüştürme işlevi çağırmak yerine dizgeyi kendin oluştur.

Örnekler

Girdi: n = 13
Çıktı: "1101"
Açıklama: 13 = 8 + 4 + 1. 8, 4, 2 ve 1'lik basamaklarda sırasıyla 1, 1, 0 ve 1 bulunur; bu da 1101 olarak okunur.

Girdi: n = 0
Çıktı: "0"
Açıklama: Sıfırın ayarlanmış biti yoktur, ancak yanıtın yine de bir basamağa ihtiyacı vardır; bu nedenle boş bir dize değil, "0" olur.

Girdi: n = 64
Çıktı: "1000000"
Açıklama: 64, 2^6 değerindedir; 64'ler basamağında tek bir 1 ve ardından 32'den 1'e kadar olan basamaklar için altı 0 gelir.

Gönderirken +16 gizli test

Ek soru

2'den 16'ya kadar herhangi bir tabana n'yi aynı döngüyü kullanarak, 9'dan büyük basamaklar için a'dan f'ye kadar olan harfleri kullanarak dönüştürebilir misin?

İpuçları

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

3 ipucundan 0 açıldı

Çözüm

İkili sayı, ikinin kuvvetlerinin toplamıdır ve her basamak, bir kuvvetin bu toplamda olup olmadığını belirtir. Basamakları en büyük basamaktan başlayarak ikinin kuvvetlerini çıkararak belirleyebilir ya da 2’ye art arda bölme işlemlerinin kalanları olarak en küçük basamaktan başlayarak okuyabilirsin. Bölme döngüsü standart yöntemdir: önce en büyük kuvveti bulmayı gerektirmez ve her taban için aynı şekilde çalışır.

Üstten ikinin kuvvetlerini çıkarın

Sezgi

Elle nasıl dönüştüreceğin şu şekildedir. n içine sığan en büyük ikinin kuvvetini bul; bu, ilk basamaktır ve 1 olur. Ardından her seferinde bir kuvvet aşağı in. Kuvvet kalan değere hâlâ sığıyorsa 1 yaz ve onu çıkar; aksi takdirde 0 yaz.

13 için en büyük kuvvet 8'dir. 1 yaz ve 5 değerini elde tut. Ardından 4 sığar (1 yaz, 1 değerini elde tut), 2 sığmaz (0 yaz) ve 1 sığar (1 yaz). Basamaklar 1101 olur. İlk basamak her zaman 1'dir, bu nedenle başta sıfır bulunamaz.

En büyük kuvveti bulmak dikkat gerektirir. power değerini n değerini geçene kadar ikiyle çarpmak, n ≥ 2^30 olduğunda 32 bitlik bir tamsayıda taşmaya neden olur; çünkü sonraki kuvvet 2^31'dir. Yalnızca power ≤ n / 2 olduğu sürece ikiyle çarpmak, n değerini hiçbir zaman aşmadan doğru kuvvette durur. 31 bitlik bir sayı 31 adım gerektirir; bu da O(log n) demektir.

Algoritma

n 0 ise "0" döndür.
power değerini 1'den başlat ve power ≤ n / 2 koşulu sağlandığı sürece iki katına çıkar.
power > 0 olduğu sürece: n ≥ power ise 1 ekle ve n değerinden power değerini çıkar; aksi hâlde 0 ekle.
power değerini yarıya indir ve tekrarla.
Eklediğin rakamları döndür.

def toBinary(n):
    if n == 0:
        return "0"
    # Largest power of two that is at most n. Comparing with n // 2 avoids overflow.
    power = 1
    while power <= n // 2:
        power *= 2
    bits = []
    while power > 0:
        if n >= power:
            bits.append("1")
            n -= power
        else:
            bits.append("0")
        power //= 2
    return "".join(bits)

2'ye tekrarlı bölme

Sezgi

n sayısının son ikili basamağı, n sayısının tek olup olmadığını, yani n % 2 değerini belirtir. 2'ye bölüp kalanı atmak, her basamağı bir konum sağa kaydırır; böylece bir sonraki basamak son basamak olur. Hiçbir şey kalmayana kadar bunu tekrarlarsın ve her basamağı en düşük basamaktan başlayarak toplarsın.

13 için: 13'ün kalanı 1, 6'nın kalanı 0, 3'ün kalanı 1 ve 1'in kalanı 1'dir; ardından sayı 0 olur. Kalanlar sırasıyla 1, 0, 1, 1 olur; ters çevrildiklerinde 1101 şeklinde okunurlar. Döngü, sayı 0'a ulaştığında durur; bu nedenle yazdığı en yüksek basamak her zaman 1 olur ve başta sıfır bulunmaz. Sıfırın kendisi döngüye hiç girmez; bu yüzden kendi kontrolünü gerektirir.

Her adımda sayı yarıya iner; bu nedenle 31 bitlik bir değer 31 adım alır, zaman karmaşıklığı O(log n) olur ve basamak dizisi O(log n) alan kullanır.

Algoritma

n 0 ise "0" döndür.
n > 0 olduğu sürece, n % 2 değerini bir basamak olarak ekle ve n değerini aşağı yuvarlanmış n / 2 olarak ayarla.
Rakamları ters çevir, çünkü en küçük basamaktan başlayarak elde edildiler.
Bunları bir dize olarak döndür.

def toBinary(n):
    if n == 0:
        return "0"
    bits = []
    while n > 0:
        # The remainder is the lowest bit that is left.
        bits.append(str(n % 2))
        n //= 2
    # The bits came out lowest first, so turn them around.
    bits.reverse()
    return "".join(bits)

Tuzaklar ve uç durumlar

Döngü kısadır ve yanlış yanıtların çoğu iki ucundan kaynaklanır.

0 için boş bir dize döndürmek. Sıfır için bölme döngüsü hiç çalışmaz, bu yüzden önce sıfırı kontrol et.
Ters çevirmeyi unutmak. Kalanlar önce en düşük basamak gelecek şekilde elde edilir; bu yüzden 6, 110 yerine 011 olarak çıkar.
JavaScript, Lua veya PHP gibi, bölme işleminin kesir döndürdüğü bir dilde / kullanmak. 13 / 2 sonucu 6 olmalı; bu nedenle aşağı yuvarla veya tamsayı bölmesi kullan.
n değerini aşana kadar ikiyle çarparak en büyük kuvveti oluşturmak. n = 2^31-1 için sonraki kuvvet olan 2^31, 32 bitlik bir tamsayıya sığmaz.
C'de yetersiz bellek ayırmak. 31 bitlik bir sayı için sonlandırıcı '\0' dahil 31 karakter gerekir.

Sıkça sorulan sorular4

Bir ondalık sayıyı ikili sayıya nasıl dönüştürürsünüz?

Sayıyı, her kalanı not ederek sayı 0'a ulaşana kadar tekrar tekrar 2'ye bölün. Kalanları sondan başa doğru okuyun. 13 için kalanlar 1, 0, 1, 1'dir; dolayısıyla 13'ün ikilik sistemdeki karşılığı 1101'dir.

Kalanlar neden ters sırada okunur?

2’ye bölme işlemlerinin ilki, sayının tek olup olmadığını, yani son ikilik basamağı gösterir. Sonraki her bölme, soldaki bir sonraki basamağı ortaya çıkarır. Yani kalanlar en düşük basamaktan başlayarak elde edilir ve sayıyı alışılmış şekilde yazmak için bunları tersine çevirirsiniz.

Ondalık sayıyı ikili sayıya dönüştürmenin zaman karmaşıklığı nedir?

Her adımda sayı yarıya iner, bu yüzden döngü ikili basamak başına bir kez çalışır; bu da yaklaşık log2(n) kez demektir. Bu, O(log n) zaman alır ve yanıt dizgesi O(log n) alan kullanır. 32 bitlik bir tamsayı için bu en fazla 31 adımdır.

Division yerine bit işlemleri kullanarak ikili sisteme dönüştürebilir misin?

Evet. n & 1 en düşük biti verir ve n >> 1 bu biti atar; bu, negatif olmayan sayılar için n % 2 ve n / 2 ile aynıdır. Döngü ve ters çevirme aynı kalır. Bölmeyi açıklamak daha kolaydır; kaydırma sürümü ise düşük seviyeli kodlarda yaygındır.

Python

def toBinary(n):
    # Kodu buraya yazın

Test durumları

Durum 1

Durum 2

Durum 3

Girdi

n = 13

Beklenen

"1101"