İlginç bir tekniği another question answer kullanılan gördüm ve biraz daha iyi anlamak istiyorum.

İşaretsiz 64-bit tamsayı verdiğimiz ve aşağıdaki bit ilgileniyoruz:

1.......2.......3.......4.......5.......6.......7.......8.......

Özellikle, bu yüzden gibi, en iyi sekiz pozisyonları devam etmek istiyoruz:

12345678........................................................

Bit . ile belirtilen değeri umursamıyoruz ve muhafaza edilmesi için yok.

solution istenmeyen bit Maskesi ve 0x2040810204081 tarafından sonucu çarpın. Bu, o çıkıyor, işe yarıyor.

Nasıl genel bu yöntem? Bu teknik bitleri alt ayıklamak için kullanılabilir mi? Nasıl bir yöntem veya bit belirli bir dizi için çalışıyor olup olmadığını anlamaz mı? Eğer

Son olarak, nasıl bir bulgu hakkında (?) gider verilen bitlerini ayıklamak için çarpan değil mi?

Çok ilginç bir soru ve zekice.

Hadi tek bir bayt manipüle almanın basit bir örnek bakın. Kullanarak basitlik için 8 bit işaretsiz. Numaranızı xxaxxbxx ab000000 istediğiniz düşünün.

Çözüm iki adımdan oluşuyordu: biraz, çarpma ardından maskeleme. Bit maskesi sıfırlar için ilginç bit döner VE basit bir işlemdir. Yukarıdaki durumda, maskeni 00100100 ve sonuç 00a00b00 olurdu.

Şimdi işin zor kısmı: ab....... dönüştüren

Bir çarpma shift-ve-ekleme işlemleri bir grup. Anahtar taşması "uzak bit olanlar da gerek kalmıyor" biz doğru yerde istiyorum. shift sağlamaktır

4 (00000100) ile çarpma her şey 2 sola kaydırmak ve 21 ** yaşattılar . b 1 ile çarpmak gerekiyor yukarı taşımak için (doğru yerde tutmak için) 4 (b yukarı taşımak için). Bu miktar 5 ve 20 ya 00010100 sihirli bir numara aldığımız önceki 4 ile birleştirilir. Orijinal maskeleme sonra 00a00b00; çarpma verir:

000000a00b000000
00000000a00b0000  
----------------
000000a0ab0b0000
xxxxxxxxab......

Bu yaklaşımdan daha fazla sayıda ve daha fazla bit için uzatabilirsiniz.

Sana sorulan sorulardan biri "bu bit herhangi bir sayı ile yapılabilir mi?" Cevap "hayır" çeşitli maskeleme işlemleri siz izin vermedikçe, ya da birkaç çarpılması. bence Sorun" - örneğin, "b" yukarıdaki sorun. sokak "çarpışmalar konudur xaxxbxxcx gibi bir numara bu yapmamız gereken hayal edin. Önceki yaklaşım aşağıdaki ihtiyacımız düşünürdüm {x 2, x {1 4 16}} = x 42 (- her şeye cevap! oooh). Sonuç:

00000000a00b00c00
000000a00b00c0000
0000a00b00c000000
-----------------
0000a0ababcbc0c00
xxxxxxxxabc......

Gördüğünüz gibi, hala çalışıyor, ama "sadece". Asıl olan şu "bit her şeyi sıkmak kadar biz de istiyoruz. arasındaki boşluk yeterli olmasıdır C d nereden örnekleri alırdım çünkü dördüncü biraz d c sonra da ekleyebilirim değil, bit taşıyabilir, ...

Resmi bir kanıt olmadan, aşağıdaki gibi sorunuzu daha çekici bölümlerine cevap verirdim: "Hayır, bu bit herhangi bir sayı için çalışmaz. N bit ayıklamak için, (N-1) ayıklamak istediğiniz bit arasında boşluk gerekir, ya da maske-çarpma ek adımlar var."

Tek istisna düşündüğüm için "olmalı (N-1) tane sıfır arasında bit" kural şudur: eğer istediğiniz ayıklamak için iki bit vardır komşu birbirini orijinal VE onları aynı sırayla, sonra yine yap. Ve amacı için (N-1) iki bit olarak sayıyorlar kural.

Başka bir fikir - @Üçlü aşağıda cevabı (yorumum yok) esinlenmiştir. Her ilginç bit için, oraya gitmek için gereken bit için yere ihtiyacınız olarak sadece sağında kaç sıfır olarak ihtiyacım var. Aynı zamanda, sonuç-bit gibi sola sola olarak kaç bit gerekir. Eğer öyleyse biraz yukarı pozisyonda n m biter, m-1 tane sıfır var soldan sağa, ve n-m sıfır onun için buna ihtiyacı var. Sonra yeniden sipariş edilecektir bit orijinal sayı aynı sırada değildir, özellikle, bu orijinal kriterleri için önemli bir gelişmedir. Bu, 16 bit word, örneğin anlamına gelir

a...e.b...d..c..

Hayatın içine

abcde...........

e ve b, d ve c arasında iki, diğerleri arasında üç arasında tek boşluk bile olsa. Ne olursa olsun N-1? Ne oldu? Bu durumda, a...e olur "blok" - 1 ile doğru yerde sonuna kadar çarpılır ve "ücretsiz e aldık". Aynı b ve d için geçerli (b, Üç boşluk ihtiyacı d sol aynı üç kişi gerekir). Biz sihirli sayı hesaplamak kopyaları mevcut bulursak:

a: << 0  ( x 1    )
b: << 5  ( x 32   )
c: << 11 ( x 2048 )
d: << 5  ( x 32   )  !! duplicate
e: << 0  ( x 1    )  !! duplicate

Eğer farklı bir sırada bu sayılar istedim açıkçası, onları daha fazla alan gerekir. Biz yeniden formüle (N-1) kural: "her zaman iş varsa en az (N-1) boşluk arasında bit; ya da, Eğer sipariş bit nihai sonucu olduğu bilinen, sonra biraz b biter pozisyon m n ihtiyacı için m-1 tane sıfır olan sol, ve n-m sıfır hakkını."

@Üçlü çekti bu kural yok tabii, olabilir bir taşıma gelen parçaları ekleyerek "sadece hakkını hedef alan" - yani, ne zaman bit aradığımız tüm olanlar. Eğer yapalım . yukarıda 16 bit word içinde sıkıca paketlenmiş beş biti ile verdiğim örneğe devam edersek:

a...e.b...d..c..

Basitlik için, 34* *bit pozisyonları isim olacak

Yapacaktık matematik oldu

ABCDEFGHIJKLMNOP

a000e0b000d00c00
0b000d00c0000000
000d00c000000000
00c0000000000000  
----------------
abcded(b c)0c0d00c00

Şimdiye kadar, düşündüm her şeyi aşağıda abcde (pozisyonlar ABCDE) farketmez, ama aslında, @Üçlü çekti, eğer b=1, c=1, d=1 (b c) pozisyon G neden biraz taşıma pozisyonu F, (d 1) pozisyon F taşımak biraz içine E - ve sonuç berbat. Faiz en az önemli bit (c bu örnekte) sağ boşluk çarpma en az önemli bit beyone gelen sıfır ile doldurma neden olacağından önemli değil, unutmayın.

(M-1) (n-m)/bizim kuralını değiştirmek gerekiyor. Eğer birden fazla bit vardır "tam olarak (n-m) kullanılmayan bit sağa saymazsak son bit desen - "c" yukarıdaki örnekte olduğu gibi), o zaman ihtiyacımız güçlendirmek için kural ve yapmamız gereken çok yinelenen!

(N-m) kriter, ama aynı zamanda olanları (n-m 1), vb karşılayan sadece bit sayısı bakmamız gerek. Hadi Q0 numarası (sonraki bit için n-m tam olarak), Q1 (n-m 1), Q(N-1) (n-1). Sonra devam edersen biz risk

Q0 > 1
Q0 == 1 && Q1 >= 2
Q0 == 0 && Q1 >= 4
Q0 == 1 && Q1 > 1 && Q2 >=2
... 

Eğer buna bakarsanız, basit bir matematiksel ifade yazarsanız görebilirsiniz

W = N * Q0   (N - 1) * Q1   ...   Q(N-1)

ve sonuç W > 2 * N sonra OLUŞTURDUĞU artırmak gerekir (n-m 1) için bir bit kriter. Bu noktada, işlemi güvenli olarak uzun W < 4; eğer bu işe yaramaz ise, kriter, vb bir daha artırmak.

Yukarıdaki aşağıdaki cevabı için uzun bir yol alacak