4
votes

La somme des bits d'ensemble des nombres de 1 à n est d'au moins k

Trouver le minimum N tel que la somme de l'ensemble des bits de nombres de 1 à N soit au moins k.

Par exemple

k = 11, output N = 7, as SB(1) + SB(2) + .. +SB(7) = 12
k = 5, output N = 4, as SB(1) + SB(2) +..+SB(4) = 5

J'ai d'abord pensé le résoudre en stocker la somme des bits définis puis appliquer une recherche binaire pour au moins k. Mais le problème ici est que 1

dynamic-programming bit

5 commentaires

Comment? Je pense que vous avez donné la formule de la somme des n premiers nombres naturels. Mais ici, l'exigence est ∑ (i = 1 à N) (Set Bit Of i)

ma faute. Maintenant je l'ai corrigé

Ok, cela pourrait aider à la place .

Je l'ai déjà vu mais je ne l'aiderai pas à cause de la grande portée

J'aurais aimé voir le lien de @ RingØ avant de faire tout ça. Ma solution est à peu près identique à cela. Comme vous le dites, la recherche binaire est la réponse, et elle fonctionne parfaitement bien - une large plage n'est pas un problème.

3 Réponses :

1
votes

Disons que votre numéro est le 13 . En binaire, il s'agit de 1101 . Déposons-le et voyons si nous pouvons voir des modèles. Je vais juste insérer quelques sauts de ligne pour vous aider plus tard. Aussi, j'ajouterai 0 , car ça ne fait pas mal (il n'a pas de bits définis).

max = 1_000_000_000_000_000_000_000_000_000
k = 1_000_000_000_000_000_000
n = (1..max).bsearch { |n|
  sum_bits_upto(n) >= k
}
# => 36397208481162321

Nous pouvons écrire tous les groupes sous n comme ceci:

def sum_bits_upto(n)
  set_bits = n.to_s(2).reverse.each_char.with_index.map { |c, b|
    b if c == "1"
  }.compact.reverse

  set_bits.each_with_index.sum { |b, i|
    (i << b) + (b << b - 1) + 1
  }
end

Notez que nous avons un groupe de taille 2 ^ 3 pour le 3ème bit de n = 1101 ; nous avons un groupe de taille 2 ^ 2 pour le 2ème bit; et un groupe de taille 2 ^ 0 pour le LSB. Appelons la taille du groupe s = 2 ^ b , où b est la position de tous les bits définis dans n (c'est-à-dire b = [ 3, 2, 0], s = [8, 4, 1] ). Remarquez les modèles de bits pour la somme la plus à droite dans chaque groupe: il y a des b colonnes de bits, et dans chaque colonne exactement s / 2 sont définis; ainsi, pour chaque bit défini, il y a 2 ^ (b-1) * b bits d'ensemble dans les colonnes les plus à droite. Mais chaque ligne a également un nombre de bits définis égal au nombre ordinal du groupe: 0, 1, 2 (comme nous ajoutons des groupes qui correspondent aux bits définis dans n ), pour le total de 2 ^ b * i + 2 ^ (b-1) * b set bits par groupe:

Group 0: 2^3*0 + 2^2*3 = 12
Group 1: 2^2*1 + 2^1*2 = 8
Group 2: 2^0*2 + 2^(-1)*0 = 2

Tout cela pour un nombre de bits set jusqu'à n-1 . Pour obtenir le nombre de bits pour n , nous devons obtenir un bit supplémentaire pour chaque bit défini dans n lui-même - ce qui correspond exactement au nombre de groupes que nous avions. Le total est donc 12 + 8 + 2 +3 = 25 .

Le voici en Ruby. Notez que 2 ^ x * y est identique à y .

             000
             001
             010
             011
             100
             101
             110
             111

1000 +       00
1000 +       01
1000 +       10
1000 +       11

1000 + 100 + |    (no digits, equal to 0 in sum)

J'espère que je n'ai pas déconné ma logique n'importe où. BTW, mon code dit qu'il y a 29761222783429247000 bits de 1 à 1_000_000_000_000_000_000 , avec seulement 24 itérations de la boucle. Cela devrait être assez rapide :)

EDIT: Apparemment, j'ai une mémoire de poisson rouge. La somme augmente de façon monotone (à chaque nombre successif, un nombre positif de bits est ajouté au total en cours). Cela signifie que nous pouvons utiliser la recherche binaire, qui devrait se concentrer sur le super-rapide cible, même si nous ne l'aidons pas en stockant des résultats intermédiaires (cela s'exécute en 0,1 s sur mon Mac):

2 commentaires

le problème n'est pas de savoir comment calculer les bits d'ensemble d'une valeur aussi grande mais comment rechercher au moins k. Comment rechercherais-je sans stocker la somme?

On y va, avec la recherche aussi.

1
votes

Poster ma réponse bien après celle d'Amadan, car elle apporte un point de vue différent sur le calcul du nombre de bits mis à N; la résolution du problème se fait via une recherche binaire qui convient car le calcul des ensembles de bits est peu coûteux

Voyons que N est une puissance de 2, comme 8

1000 => 3 x 8/2 +1 = 13  + 0      (no 1 left)
0100 => 2 x 4/2 +1 =  5  + 4 x 1  (one bit on the left, the 8)
0001 => 0 x 1/2 +1 =  1  + 1 x 2  (the 8 and the 4)

Dans la colonne a nous avons alternativement 1 et 0 , dans la colonne b le même mais tous les deux (2 ¹) nombres, et en c tous les quatre (2 ²).

Quoi qu'il en soit, nous obtenons le même nombre de 1 dans chaque colonne, N / 2. Ainsi, le nombre de 1 jusqu'à une puissance de 2 est (+1 pour la puissance de 2 elle-même)

journal ₂ (N) * N / 2 + 1

Tout entier étant une somme de puissance de 2, comme pour 13

1000 + 0100 + 0001

le nombre de 1 jusqu'à N est la somme de l'équation ci-dessus pour chacune des 2 puissances de N, en ajoutant les 1 s sur le côté gauche pour chaque puissance x = 2 ^{P sup > (puisque pour compter jusqu'à cette puissance, les bits de puissance supérieurs> P sont là)}

bitsets = P * x / 2 + 1 + x * nombre de bits mis à gauche à cette puissance x p >

Par exemple pour 13 ₁₀

Il y en a 25 1 jusqu'à 13 .

Le calcul est O (log (N)) ce qui est rapide, même pour 10 ¹⁸ (environ 60 itérations) .

Une recherche binaire fonctionnera en O (log ²), trouvant le max k étant le nombre de bits mis de 1 à la puissance sur 2 au-dessus de 10 ¹⁸, que l'on peut calculer grâce à la formule ci-dessus.

0 commentaires

1
votes

J'ai aimé la question, alors j'ai passé du temps à la coder. Le code Python ci-dessous fonctionne avec les positions des bits, donc la complexité est limitée au nombre de bits maximum présents dans 10 ^ 18.

# Store sum of 1-bits upto max number formed by N bits.
# For example - sumToNBits of 1 bit is 1, 2 bit numbers 01,10,11 is 4 and 3 bit 
# numbers 01,10,11,100,101,110,111 is 12
# and so on.

sumToNBits = []
prevSum = 0
for i in range(1, 65):
    prevSum = (1 << (i-1)) + 2*prevSum
    sumToNBits.append(prevSum)


# Find maximum possible number (2 to power P - 1) which has sum of 1-bits up to K.
def findClosestPowerTwo(K):
    index = 1
    prevEntry = 0
    for entry in sumToNBits: 
        if (entry > K):
            return (K-prevEntry, index-1)
        prevEntry = entry
        index += 1

    return (K-prevEntry, index-1)

# After finding max 2 to power P, now increase number up to K1 = K - bits used by 2 to power P.
def findNextPowerTwo(K, onBits):
    index = 1
    prevTotalBits = 0
    totalBits = onBits * ((1 << index) - 1) + sumToNBits[index-1]

    while(K >= totalBits):
        prevTotalBits = totalBits
        index += 1
        totalBits = onBits * ((1 << index) - 1) + sumToNBits[index-1]

    return (K-prevTotalBits, index-1)



def findClosestNumber(K):
    (K, powerTwo) = findClosestPowerTwo(K)
    number = (1 << (powerTwo)) - 1

# Align to 2 to power P
    if (K >= 1):
        K = K - 1
        number += 1
    onBits = 1

    while(K > 0):
        (K, powerTwo) = findNextPowerTwo(K, onBits)

        if (powerTwo == 0):
            return number+1

        number += ((1 << (powerTwo)) - 1)

# Align to 2 to power P
        if (K >= (onBits + 1)):
            K = K - (onBits + 1)
            number += 1
        onBits += 1

    return number

num = 1
while num < 100:
    print(num, end = " ")
    print(findClosestNumber(num))
    num += 1

0 commentaires