toplamı ayrı bir güç Yani

Question

dahil, biz 2 güçlerinin toplamıdır bazı dizi var:

örnek 308 = 256 + 32 + 16 + 4

için bilmek için bir yol var mı 2'nin ayrı gücüdür bu sınıfa dahil mi?

Örneğin, 32 (2'nin gücündeki 2) dahildir.

Ancak 8 (2'nin 2'si gücünde değil).

Bunun için bazı formül var mı?

Answer 1

Evet. (1 << i)2^i anlamına gelirken Basitçe

if (n & (1 << i)) { 
    it is included 
} 

kontrol edin.

Özel durumunuz için if (308 & (1 << 5)) { /* ... */ } ile 32=2^5.

Artık düzeltilmiş yorum ekledim. Temsili bağımsız bir formül olduğunu düşünmüyorum (bunun anlamı, bir closed-form expression demek).

dahil araçlar "Biz iki güçlerin toplamı olarak n yazmak isterseniz sayı 2^i görünmesi gerektiğini" dizi durumda 2^i "dahil" olup olmadığını kontrol etmek elbette apaçık bir algoritma var. (Bu temelde zaten bilgisayarda ikilik temsil olduğunu n ikili gösterimi, bilgisayar unutmayın.)

int k = 0; 
while (n > 0) { 
    if (k == i && n % 2 == 0) { 
     /* contained */ 
    } 
    k++; 
    n /= 2; 
}