Question à propos de round_up macro

#define ROUND_UP(N, S) ((((N) + (S) - 1) / (S)) * (S))

Avec la macro ci-dessus, quelqu'un pourrait-il m'aider sur la compréhension de l' "(s)-1" partie, pourquoi?

et aussi des macros comme:

#define PAGE_ROUND_DOWN(x) (((ULONG_PTR)(x)) & (~(PAGE_SIZE-1)))
#define PAGE_ROUND_UP(x) ( (((ULONG_PTR)(x)) + PAGE_SIZE-1)  & (~(PAGE_SIZE-1)) )

Je sais "(~(PAGE_SIZE-1)))" la partie est égal à zéro les cinq derniers bits, mais d'autres que je suis paumé, en particulier le rôle de "& " opérateur joue.

Merci,

OriginalL'auteur user124858 | 2009-06-18

  1. 16

    La ROUND_UP macro est en s'appuyant sur la division entière pour faire le travail. Il ne fonctionne que si les deux paramètres sont des entiers. Je suis en supposant que N est le nombre à arrondir et S est l'intervalle de temps sur lequel il doit être arrondi. C'est, ROUND_UP(12, 5) doit retourner à 15, depuis le 15 est le premier intervalle de 5 plus de 12.

    Imaginer nous avons arrondi vers le bas au lieu de vers le haut. Dans ce cas, la macro serait tout simplement:

    #define ROUND_DOWN(N,S) ((N / S) * S)

    ROUND_DOWN(12,5) serait de retour 10, parce que (12/5) en entier de la division est de 2, et 2*5 est de 10. Mais nous ne faisons pas ROUND_DOWN, nous faisons ROUND_UP. Donc avant de faire la division entière, nous voulons ajouter autant que nous le pouvons sans perdre de précision. Si nous avons ajouté S, il travail dans presque tous les cas; ROUND_UP(11,5) allait devenir (((11+5) /5) * 5), et depuis 16/5 dans la division entière est 3, nous aurions 15.

    Le problème vient quand on passe un certain nombre qui est déjà arrondi au multiple spécifié. ROUND_UP(10, 5) serait de retour 15, et c'est mauvais. Ainsi, au lieu de l'ajout S, nous ajoutons S-1. Cela garantit que nous ne serons jamais à pousser quelque chose jusqu'à la prochaine "seau" inutilement.

    La PAGE_ macros ont à voir avec les mathématiques binaires. Nous allons faire semblant que nous sommes face à des 8 bits des valeurs pour des raisons de simplicité. Supposons que PAGE_SIZE est 0b00100000. PAGE_SIZE-1 est donc 0b00011111. ~(PAGE_SIZE-1) est alors 0b11100000.

    Binaire & seront sur la ligne de deux nombres binaires et laisser un 1 quelque part que les deux nombres avaient 1. Ainsi, si x était 0b01100111, l'opération devrait se dérouler comme suit:

      0b01100111  (x)
& 0b11100000  (~(PAGE_SIZE-1))
------------
  0b01100000

    Vous remarquerez que l'opération de vraiment seulement remis à zéro-les 5 derniers bits. C'est tout. Mais c'est exactement ce que l'opération était nécessaire arrondie au plus proche de l'intervalle de PAGE_SIZE. Notez que cela n'a fonctionné parce que PAGE_SIZE était exactement une puissance de 2. C'est un peu comme dire que pour n'importe quel nombre décimal, vous pouvez arrondir au plus proche de 100 simplement par la mise à zéro-les deux derniers chiffres. Il fonctionne parfaitement, et il est vraiment facile à faire, mais ne fonctionne pas à tous si vous avez essayé d'arrondir au multiple le plus proche de 76.

    PAGE_ROUND_UP fait la même chose, mais il ajoute qu'il peut à la page avant de la couper. C'est un peu comme la façon dont je peux arrondi au plus proche multiple de 100 par l'ajout de 99 à n'importe quel nombre et puis mise à zéro-les deux derniers chiffres. (Nous ajoutons PAGE_SIZE-1 pour la même raison, nous avons ajouté S-1 ci-dessus).

    Bonne chance avec votre mémoire virtuelle!

    OriginalL'auteur BJ Homer

  2. 4

    En utilisant l'arithmétique des nombres entiers, en divisant toujours arrondi vers le bas. Pour remédier à cela, vous ajoutez le plus grand nombre possible qui n'affectera pas le résultat si le premier nombre est divisible. Pour le nombre S, que le plus grand nombre possible est S-1.

    Arrondi à une puissance de 2 est spécial, parce que vous pouvez le faire avec les opérations sur les bits. Un multiple de 2 cadeaux à zéro dans le fond bits, un multiple de 4 aura toujours de zéro dans la partie inférieure de deux bits, etc. La représentation binaire d'une puissance de 2 est un peu unique suivie par un tas de zéros; en soustrayant 1 sera clair que les bits, les bits vers la droite. L'inversion de la valeur crée un masque de bits avec des zéros dans les endroits qui ont besoin d'être clarifiés. Le & opérateur va effacer les bits de votre valeur, donc l'arrondi de la valeur vers le bas. La même astuce de l'ajout (PAGE_SIZE-1) à la valeur d'origine qu'il provoque, pour arrondir vers le haut au lieu de vers le bas.

    OriginalL'auteur Mark Ransom

  3. 1

    La page d'arrondi macros supposons que des PAGE_SIZE est une puissance de deux, tels que:

    0x0400    -- 1 KiB
0x0800    -- 2 KiB`
0x1000    -- 4 KiB

    La valeur de PAGE_SIZE - 1, par conséquent, est tout un bits:

    0x03FF
0x07FF
0x0FFF

    Par conséquent, si les entiers de 16 bits (au lieu de 32 ou 64 il me permet de gagner un peu de temps), alors la valeur de ~(PAGE_SIZE-1) est:

    0xFC00
0xFE00
0xF000

    Lorsque vous prenez la valeur de x (en supposant que, de manière invraisemblable pour la vraie vie, mais suffisante pour les besoins de l'exposé, que ULONG_PTR est un entier non signé entier 16 bits) est 0xBFAB, puis

    PAGE_SIZE         PAGE_ROUND_DN(0xBFAB)   PAGE_ROUND_UP(0xBFAB)

0x0400     -->    0xBC00                  0xC000
0x0800     -->    0xB800                  0xC000
0x1000     -->    0xB000                  0xC000

    Les macros tour vers le bas et jusqu'à la plus proche multiple de la taille de page. Les cinq derniers bits ne serait remis à zéro si PAGE_SIZE == 0x20 (ou 32).

    OriginalL'auteur Jonathan Leffler

  4. 1

    Basé sur l'actuel projet de norme (C99) cette macro n'est pas tout à fait correct, cependant, de noter que, pour les valeurs négatives de N le résultat sera presque certainement être incorrect.

    La formule:

    #define ROUND_UP(N, S) ((((N) + (S) - 1) / (S)) * (S))

    Utilise le fait que la division entière arrondit vers le bas pour les entiers non négatifs et utilise le S - 1 partie pour le forcer à tour à la place.

    Cependant, la division entière tours vers zéro (C99, Section 6.5.5. Multiplicatif opérateurs, point 6). Pour le négatif,N, la bonne façon d'arrondir est:"N /S', rien de plus, rien de moins.

    Il devient encore plus impliqué si S est également autorisé à être une valeur négative, mais nous allons même pas y aller... (voir: Comment puis-je m'assurer qu'une division de nombres entiers est toujours arrondi? pour une discussion plus détaillée de divers mauvais et une ou deux bonnes solutions)

    OriginalL'auteur jerryjvl

  5. 0

    Le & en fait si.. bon ok, permet de prendre certains nombres binaires.

    (avec 1000 étant la taille de la page) 
PAGE_ROUND_UP(01101b)= 
01101b+1000b-1b & ~(1000b-1b) = 
01101b+111b & ~(111b) = 
01101b+111b & ...11000b = (... signifie 1 est continue pour la taille de l'ULONG) 
10100b & 11000b= 
10000b

    Donc, comme vous pouvez le voir(je l'espère), Ce arrondit en ajoutant PAGE_SIZE à x puis ANDing de sorte qu'il annule les bas morceaux de PAGE_SIZE qui ne sont pas définis

    OriginalL'auteur Earlz