Algorithme pour calculer le nombre de 1 pour une plage de nombres en binaire

Question

Donc, je viens de rentrer de l' ACM de Programmation de la concurrence et fait très bien, mais il y avait un problème que pas un seul de l'équipe a obtenu.

Le Problème.

Commencez avec un entier N0 qui est plus grand que 0. Laissez-N1-être le nombre de ceux dans la représentation binaire de N0. Donc, si N0 = 27, N1 = 4. Pour tous i > 0, laissez Ni le nombre de ceux dans la représentation binaire de l' Ni-1. Cette séquence sera toujours converger vers un. Pour n'importe quel nombre de départ, N0, soit K la valeur minimale de i >= 0 pour lequel N1 = 1. Par exemple, si N0 = 31, alors N1 = 5, N2 = 2, N3 = 1, donc K = 3.

En partant d'une série de numéros consécutifs et une valeur de X le nombre de numéros de la gamme ont une valeur de K égale à X?

Entrée
Il y aura plusieurs cas de test dans l'entrée. Chaque cas de test se compose de trois nombres entiers sur une seule ligne: LO HI X
Où LO et HI (1 <= LO <= HI <= 10^18) sont les limites inférieure et supérieure d'une plage de nombres entiers, et X (0 <= X <= 10) est la valeur cible pour K. L'entrée se termine avec une ligne de trois 0s.

Sortie
Pour chaque cas de test de la sortie d'un nombre entier représentant le nombre d'entiers dans la gamme à partir de LO de HI (inclus) qui ont une valeur de K égale à X dans l'entrée. Imprimer chaque Entier sur sa propre ligne, sans espace. N'imprimez pas de lignes vides entre les réponses.

D'Entrée D'Échantillon

31 31 3
31 31 1
27 31 1
27 31 2
1023 1025 1
1023 1025 2
0 0 0

Exemple De Sortie

1
0
0
3
1
1

---

Les gars si vous voulez je peut comprendre notre réponse ou notre problème, parce que la recherche d'une petite plage est facile, mais je vais vous donner un indice d'abord votre programme doit s'exécuter en secondes, pas des minutes. Nous avons eu une bonne solution, mais pas un algorithme efficace d'utiliser une gamme similaire à

48238 10^18 9

De toute façon bonne chance et si la communauté aime ces nous avons eu plus de nous n'est pas la solution qui pourrait être un bon casse-tête pour vous les gars. La concurrence permet d'utiliser Python, C++, ou Java-tous les trois sont acceptables dans une réponse.

---

Donc, comme un soupçon de mon entraîneur lui a dit de penser de façon binaire nombres comptent plutôt que de vérifier chaque bit. Je pense que nous obtient de beaucoup plus près.

Answer 1

Je pense que la clé est d'abord bien comprendre le modèle de valeurs de K et la vitesse à laquelle il grandit. Fondamentalement, vous avez:

K(1) = 0
K(X) = K(bitcount(X))+1 for X > 1

Afin de trouver la plus petite des valeurs de X pour un certain K nous voir

K(1) = 0
K(2) = 1
K(3) = 2
K(7) = 3
K(127) = 4
K(170141183460469231731687303715884105727) = 5

Donc, pour un exemple comme 48238 10^18 9 la réponse est trivialement 0. K=0 que de 1, et K=1 uniquement pour des puissances de 2, donc dans la gamme de l'intérêt, nous allons à peu près seulement, voir les valeurs de K de 2, 3 ou 4, et de ne jamais voir K >= 5

modifier

Ok, donc nous sommes à la recherche pour un algorithme permettant de compter le nombre de valeurs avec K=2,3,4 dans une gamme de valeur de LO..SALUT sans une itération sur l'ensemble de la gamme. Donc, la première étape est de trouver le nombre de valeurs dans la plage avec bitcount(x)==i pour i = 1..59 (puisque nous ne se soucient que des valeurs jusqu'à 10^18 et 10^18 < 2^60). Afin de briser la plage de lo..hi en sous-plages qui sont une puissance de 2 la taille et ne diffèrent que dans leur bas de n bits -- une série de la forme x*(2^n)..(x+1)*(2^n)-1. Nous pouvons décomposer la arbitray lo..hi range dans ces sous-plages facilement. Pour chaque sous-intervalle, il y aura à choisir(n, i) les valeurs avec i+bitcount(x) bits. Nous avons donc ajouter tous les sous-plages pour obtenir un vecteur de compte pour 1..59, qui nous a ensuite itérer sur, l'addition de ces éléments avec la même valeur de K pour obtenir notre réponse.

edit (fixé à nouveau à être C89 compatible et le travail pour lo=1/k=0)

Voici un programme en C pour faire ce que j'ai décrit précédemment:

#include <stdio.h>
#include <string.h>
#include <assert.h>

int bitcount(long long x) {
    int rv = 0;
    while(x) { rv++; x &= x-1; }
    return rv; }

long long choose(long long m, long long n) {
    long long rv = 1;
    int i;
    for (i = 0; i < n; i++) {
        rv *= m-i;
        rv /= i+1; }
    return rv; }

void bitcounts_p2range(long long *counts, long long base, int l2range) {
    int i;
    assert((base & ((1LL << l2range) - 1)) == 0);
    counts += bitcount(base);
    for (i = 0; i <= l2range; i++)
        counts[i] += choose(l2range, i); }

void bitcounts_range(long long *counts, long long lo, long long hi) {
    int l2range = 0;
    while (lo + (1LL << l2range) - 1 <= hi) {
        if (lo & (1LL << l2range)) {
            bitcounts_p2range(counts, lo, l2range);
            lo += 1LL << l2range; }
        l2range++; }
    while (l2range >= 0) {
        if (lo + (1LL << l2range) - 1 <= hi) {
            bitcounts_p2range(counts, lo, l2range);
            lo += 1LL << l2range; }
        l2range--; }
    assert(lo == hi+1); }

int K(int x) {
    int rv = 0;
    while(x > 1) {
        x = bitcount(x);
        rv++; }
    return rv; }

int main() {
    long long counts[64];
    long long lo, hi, total;
    int i, k;
    while (scanf("%lld%lld%d", &lo, &hi, &k) == 3) {
        if (lo < 1 || lo > hi || k < 0) break;
        if (lo == 0 || hi == 0 || k == 0) break;
        total = 0;
        if (lo == 1) {
            lo++;
            if (k == 0) total++; }
        memset(counts, 0, sizeof(counts));
        bitcounts_range(counts, lo, hi);
        for (i = 1; i < 64; i++)
            if (K(i)+1 == k)
                total += counts[i];
        printf("%lld\n", total); }
    return 0; }

qui fonctionne très bien pour des valeurs jusqu'à 2^63-1 (LONGLONG_MAX). Pour 48238 1000000000000000000 3 il donne 513162479025364957, ce qui semble plausible

modifier

donner les entrées de

48238 1000000000000000000 1
48238 1000000000000000000 2
48238 1000000000000000000 3
48238 1000000000000000000 4

donne sorties de

44
87878254941659920
513162479025364957
398959266032926842

Ceux d'ajouter jusqu'à 999999999999951763 ce qui est correct. La valeur de k=1 est correcte (il y a 44 puissances de deux dans la gamme de 2^16 jusqu'à 2^59). Ainsi, alors que je ne suis pas sûr que les 3 autres valeurs sont correctes, elles ne sont certainement plausible.

Answer 2

L'idée derrière cette réponse peut vous aider à développer très rapidement une solution. Avoir des plages de 0..2^N la complexité d'un potentiel algorithme O(N) dans le pire des cas (en Supposant que la complexité d'un long calcul est O(1)) Si elle est programmée correctement, il devrait facilement manipuler N = 1000000 en quelques millisecondes.

Imaginez, nous avons les valeurs suivantes:

LO   =          0; (0000000000000000000000000000000)
HI   = 2147483647; (1111111111111111111111111111111)

Le plus bas possible N1 dans la plage de LO..SALUT 0 Le plus élevé possible N1 dans la plage de LO..HI est de 31

Donc le calcul de N2..NN partie est faite que pour l'un des 32 valeurs (0..31). Ce qui peut être fait simplement, même sans ordinateur. Maintenant passons à calculer le montant de N1=X pour une plage de valeurs LO..SALUT

Lorsque nous avons X = 0, nous avons count(N1=X) = 1 c'est la valeur suivante:

1   0000000000000000000000000000000

Lorsque nous avons X = 1, nous avons count(N1=X) = 31 ce sont les valeurs suivantes:

01  1000000000000000000000000000000
02  0100000000000000000000000000000
03  0010000000000000000000000000000
    ...
30  0000000000000000000000000000010
31  0000000000000000000000000000001

---

Lorsque nous avons X = 2, nous avons le schéma suivant:

1100000000000000000000000000000

Combien de chaînes uniques peut être formé de 29 '0' et de 2 '1'?

Imaginez le plus à droite de '1'(#1) est le vélo de gauche à droite, nous obtenons l'image suivante:

01  1100000000000000000000000000000
02  1010000000000000000000000000000
03  1001000000000000000000000000000
    ...
30  1000000000000000000000000000001 

Maintenant, nous avons plus de 30 chaînes en déplaçant le " 1 " (#1) de gauche à droite, il est maintenant impossible de créer une chaîne unique en déplaçant le " 1 " (#1) dans n'importe quelle direction. Cela signifie que nous devrions aller à '1'(#2) vers la droite, nous allons également réinitialiser la position de '1'(#1) que de la gauche que possible en restant unicité, nous obtenons:

01  0110000000000000000000000000000

maintenant, nous ne le vélo de '1'(#1) une fois de plus

02  0101000000000000000000000000000
03  0100100000000000000000000000000
    ...
29  0100000000000000000000000000001

Maintenant, nous avons du 29 chaînes uniques, de la poursuite de cette opération 28 fois nous obtenons l'expression suivante

count(N1=2) = 30 + 29 + 28 + ... + 1 = 465

---

Lorsque nous avons X = 3 l'image reste similaire, mais nous allons de l''1'(#1), '1'(#2), '1'(#3)

Déplacer le " 1 " (#1) crée 29 chaînes uniques, lorsque nous avons commencer à bouger '1'(#2) nous obtenons

29 + 28 + ... + 1 = 435 chaînes uniques, après qu'il nous reste à traiter de '1'(#3) nous avons donc

29 + 28 + ... + 1 = 435
     28 + ... + 1 = 406
          ...
              + 1 = 1

435 + 406 + 378 + 351 + 325 + 300 + 276 +
253 + 231 + 210 + 190 + 171 + 153 + 136 +
120 + 105 + 091 + 078 + 066 + 055 + 045 +
036 + 028 + 021 + 015 + 010 + 006 + 003 + 001 = 4495

---

Nous allons essayer de résoudre le cas général, c'est à dire quand on a N zéros et M celles. Montant global de permutations pour la chaîne de caractères de longueur (N + M) est égale à (N + M)!

Le montant de '0' doublons dans cette chaîne est égal à N! Le nombre de " 1 " doublons dans cette chaîne est égale à M!

en recevant ainsi la quantité globale de chaînes uniques formé de N zéros et M est

              (N + M)!          32!       263130836933693530167218012160000000
F(N, M) =  ============= => ========== = ====================================== = 4495
            (N!) * (M!)      3! * 29!      6 * 304888344611713860501504000000

Edit:

F(N, M) = Binomial(N + M, M)

---

Prenons maintenant un exemple réel:

LO   =   43797207; (0000010100111000100101011010111)
HI   = 1562866180; (1011101001001110111001000000100)

Alors, comment pouvons-nous appliquer notre unique permutations formule à cet exemple? Puisque nous ne savons pas comment beaucoup de " 1 "est situé en dessous de LO et de la façon dont beaucoup de" 1 " est situé au-dessus de SALUT.

Donc permet de compter ces permutations ci-dessous LO et HI.

Rappelons-nous comment nous avons parcouru '1'(#1), '1'(#2), ...

1111100000000000000000000000000 => 2080374784
1111010000000000000000000000000 => 2046820352
1111001000000000000000000000000 => 2030043136
1111000000000000000000000000001 => 2013265921

1110110000000000000000000000000 => 1979711488
1110101000000000000000000000000 => 1962934272
1110100100000000000000000000000 => 1954545664
1110100010000000000000000000001 => 1950351361

Comme vous le voyez, ce vélo processus diminue les valeurs décimales en douceur. Nous avons donc besoin de compter la quantité de cycles jusqu'à ce que nous atteignons SALUT valeur. Mais nous ne devrions pas compter ces valeurs par un parce que le pire des cas, peut générer jusqu'à 32!/(16!*16!) = 601080390 cycles, ce qui nous permettra d'être à vélo très longtemps :) Nous avons donc besoin d'cycle des morceaux de '1' à la fois.

Le fait d'avoir notre exemple, nous voulons compter le montant des cycles de transformation

1111100000000000000000000000000 => 1011101000000000000000000000000
                                   1011101001001110111001000000100

Alors, combien de cycles provoque la transformation

1111100000000000000000000000000 => 1011101000000000000000000000000

?

Permet de voir, à la transformation:

1111100000000000000000000000000 => 1110110000000000000000000000000

est égal à l'ensemble des cycles:

01  1111100000000000000000000000000
02  1111010000000000000000000000000
...
27  1111000000000000000000000000001
28  1110110000000000000000000000000

Nous avons donc besoin d'28 cycles de transformer

1111100000000000000000000000000 => 1110110000000000000000000000000

Combien de cycles devons-nous transformer

1111100000000000000000000000000 => 1101110000000000000000000000000

l'exécution se déplace suivant nous avons besoin de:

1110110000000000000000000000000 28 cycles
1110011000000000000000000000000 27 cycles
1110001100000000000000000000000 26 cycles
...
1110000000000000000000000000011  1 cycle

et 1 cycle pour la réception:

1101110000000000000000000000000  1 cycle

ainsi, la réception de 28 + 27 + ... + 1 + 1 = 406 + 1

mais nous avons vu cette valeur avant et c'était le résultat pour le montant de l'unique permutations, qui a été calculée pour 2 '1' et 27 '0'. Cela signifie que la quantité de cycles tout en se déplaçant

11100000000000000000000000000 => 01110000000000000000000000000

est égal au déménagement

_1100000000000000000000000000 => _0000000000000000000000000011 

plus un autre cycle

donc, cela signifie que si nous avons M zéros et N et souhaitez déplacer le bloc de U '1' à la droite, nous aurons besoin de procédez de la manière suivante quantité de cycles:

      (U - 1 + M)!
1 + =============== = f(U, M)
     M! * (U - 1)!

Edit:

f(U, M) = 1 + Binomial(U - 1 + M, M)

Revenons maintenant à notre exemple réel:

    LO   =   43797207; (0000010100111000100101011010111)
    HI   = 1562866180; (1011101001001110111001000000100)

donc, ce que nous voulons faire est de compter la quantité de cycles nécessaires pour effectuer les tâches suivantes transformations (supposons que N1 = 6)

1111110000000000000000000000000 => 1011101001000000000000000000000
                                   1011101001001110111001000000100

elle est égale à:

1011101001000000000000000000000    1011101001000000000000000000000
-------------------------------    -------------------------------
_111110000000000000000000000000 => _011111000000000000000000000000 f(5, 25) = 118756
_____11000000000000000000000000 => _____01100000000000000000000000 f(2, 24) = 301
_______100000000000000000000000 => _______010000000000000000000000 f(1, 23) = 24
________10000000000000000000000 => ________01000000000000000000000 f(1, 22) = 23

donc 119104 "perdu" des cycles qui sont situés au-dessus de SALUT

Quant à LO, il n'y a effectivement pas de différence dans quelle direction nous sommes à vélo donc, pour le calcul de LO, nous pouvons faire la randonnée à vélo:

0000010100111000100101011010111    0000010100111000100101011010111
-------------------------------    -------------------------------
0000000000000000000000000111___ => 0000000000000000000000001110___ f(3, 25) = 2926
00000000000000000000000011_____ => 00000000000000000000000110_____ f(2, 24) = 301

Donc 3227 "perdu" des cycles qui sont situés en dessous de LO cela signifie que

overall amount of lost cycles = 119104 + 3227 = 122331

overall amount of all possible cycles = F(6, 25) = 736281

N1 in range 43797207..1562866180 is equal to 736281 - 122331 = 613950

J'ai l'habitude de fournir à la partie restante de la solution. Il n'est pas difficile de saisir la partie restante. Bonne chance!

Answer 3

Je pense que c'est un problème en mathématiques discrètes,
en supposant que LOW est 0,
sinon, nous pouvons insérer une fonction pour additionner les nombres en dessous de LOW,
à partir des chiffres indiqués, je comprends que le plus long nombre comprendra jusqu'à 60 chiffres binaires au plus

 alg(HIGH,k)

l=len(HIGH)
sum=0;

for(i=0;i<l;i++)
{
 count=(l choose i); 
 nwia=numbers_with_i_above(i,HIGH); 
 if canreach(i,k) sum+=(count-nwia);
}
 

tous les chiffres apparaissent
non est répertorié deux fois
number_with_i_above est trivial
canreach avec des nombres jusqu'à 60 est facile
len est-il la longueur d'une représentation binaire

Answer 4

Zobgib,

La clé de ce problème n'est pas de comprendre comment rapidement la croissance de K du modèle augmente, mais la FAÇON dont elle se développe, elle-même. La première étape est de comprendre (comme votre entraîneur lui a dit) combien de nombres binaires compter, comme ce qui détermine tout sur la façon dont K est déterminé. Nombres binaires suivre un modèle qui se distingue lors du calcul du nombre de positifs bits. Son une seule progressive motif répétitif. Je vais faire d'une manière inhabituelle...

Supposons i est un entier de valeur. Supposons que b est le nombre de positifs bits dans je
i = 1; 
b = 1; 

i = 2; 3;
b = 1; 2;

i = 4; 5; 6; 7;
b = 1; 2; 2; 3;

j'= 8; 9; 10; 11; 12; 13; 14; 15;
b = 1; 2; 2; 3; 2; 3; 3; 4;

j'= 16; 17; 18; 19; 20; 21; 22; 23; 24; 25; 26; 27; 28; 29; 30; 31;
b = 1; 2; 2; 3; 2; 3; 3; 4; 2; 3; 3; 4; 3; 4; 4; 5; 

Je vous assure, cette tendance est à l'infini, mais si nécessaire, vous
devrait être en mesure de trouver ou de construire une preuve facilement.

Si vous regardez les données ci-dessus, vous remarquerez un motif distinct lié à 2^n. Chaque fois que vous avez un entier exposant de 2, le modèle est de réinitialiser y compris chaque terme du modèle précédent, et ensuite, chaque terme de la précédente motif incrémenté de 1. En tant que tel, pour obtenir K, vous venez de demander le nouveau numéro du modèle ci-dessus. La clé est de trouver une expression unique (c'est efficace) pour recevoir votre nombre de bits.

Pour la démonstration, encore une fois, vous pouvez extrapoler un nouveau modèle hors de cela, parce qu'il est statique et suit la même progression. Ci-dessous est à l'origine des données modifiées avec sa valeur de K (basé sur la récursivité).

Supposons i est un entier de valeur. Supposons que b est le nombre de positifs bits dans je
i = 1; 
b = 1; 
K = 1;

i = 2; 3;
b = 1; 2;
K = 1; 2;

i = 4; 5; 6; 7;
b = 1; 2; 2; 3;
K = 1; 2; 2; 3;

j'= 8; 9; 10; 11; 12; 13; 14; 15;
b = 1; 2; 2; 3; 2; 3; 3; 4;
K = 1; 2; 2; 3; 2; 3; 3; 2;

j'= 16; 17; 18; 19; 20; 21; 22; 23; 24; 25; 26; 27; 28; 29; 30; 31;
b = 1; 2; 2; 3; 2; 3; 3; 4; 2; 3; 3; 4; 3; 4; 4; 5; 
K = 1; 2; 2; 3; 2; 3; 3; 2; 2; 3; 3; 2; 3; 2; 2; 3;

Si vous remarquez, K suit une structuration similaire, avec une condition spéciale... à Chaque fois que b est une puissance de 2, il réduit en fait la valeur de K par 2. Donc, si vous suivez un binaire progression, vous devriez être en mesure de faire correspondre facilement votre K valeurs. Depuis, ce modèle est personne à charge sur des puissances de 2, et le motif est personne à charge sur la découverte de la puissance de 2 la plus proche et à partir de là, je propose la solution suivante. Prenez votre LOW de la valeur et de trouver le plus proche de puissance de 2 (p) telle qu' 2^p < LOW. Cela peut être fait par "compter les bits" pour le numéro le plus bas. Encore une fois, une fois que vous savez qui l'exposant qu'il est, vous n'avez pas à compter les bits pour n'importe quel autre nombre. Vous avez juste incrémenter par le modèle et vous aurez votre b et donc K (qui est la même chose).

Remarque: Si vous êtes particulièrement attentif, vous pouvez utiliser la précédente b ou K pour déterminer le prochain. Si le courant i est impair, ajouter 1 à la précédente b. Si le courant i est divisible par 4, alors vous décrémenter b soit 1 ou 2, selon qu'il s'agisse de la première 1/2 du motif ou de la deuxième moitié. Et, bien sûr, si i est une puissance de 2, recommencer à partir de 1.

Fuzzical Logique

Pseudo-code d'Exemple (non Optimisé)

{   var LOW, HIGH
    var power = 0

//Obtenir La Puissance De 2 La Plus Proche for (var i = 0 à 60) { // Le comparer au niveau du bit ET si (FAIBLE bitAND (2 ^ i) = (2 ^ i)) { si ((2 ^ i) <= LOW) { régler la puissance de je } else { // Trouvé que la Puissance: fin de la boucle for j'61 } } }

// Automatiquement 1 à une Puissance de 2 ensemble numOfBits à 1 tableau numbersWithPositiveBits avec 64 entiers = 0 // Qui doit créer le schéma de Puissance de 2 ensemble foundLOW à false for (var j = (2^puissance) à ÉLEVÉ) { ensemble lenOfPatten à (puissance + 1) // Ne pas enregistrer jusqu'à ce que nous avons trouvé la FAIBLE valeur si ((foundLOW est faux) bitAND (j est égal à FAIBLE)) { ensemble foundLOW de vrai } // Si j est impair, incrémenter numOfBits si ((1 bitAND j) est égal à 1) { incrément numOfBits } else if (j module 4 == 0) { décrémenter numOfBits en conséquence //celui-ci vous-même, veuillez } else if ((j - (2^puissance)) == (puissance + 1)) { // Nous sommes à la prochaine incrément de puissance // Début de motif ensemble numOfBits à 1 } // Enregistrement le cas échéant si (foundLOW est égale à true) { incrément élément numOfBits dans la gamme numbersWithPositiveBits } }

// À partir d'ici, et d'en tirer vos valeurs de K.

Answer 5

Vous pouvez résoudre ce problème efficacement comme suit:

 ret = 0;
for (i = 1; i <= 64; i++) {
  if (computeK(i) != desiredK) continue;
  ret += numBelow(HIGH, i) - numBelow(LO - 1, i);
}
return ret;
 

La fonction numBelow(high, numSet) calcule le nombre d'entiers inférieur ou égal à high et supérieur à zéro pour lesquels numSet bits sont définis. Pour implémenter numBelow(high, numSet) efficacement, vous pouvez utiliser quelque chose comme ceci:

 numBelow(high, numSet) {
  t = floor(lg(high));
  ret = 0;
  if (numBitsSet(high) == numSet) ret++;
  while (numSet > 0 && t > 0) {
    ret += nchoosek(t - 1, numSet);
    numSet--;
    while (--t > 0 && (((1 << t) & high) == 0));
  }
  return ret;
}