Compter les bits non nuls: banal !!!

William VOIROL Messages postés 261 Date d'inscription mardi 12 décembre 2006 Statut Membre Dernière intervention 10 juin 2019 - 3 févr. 2014 à 06:43
BruNews Messages postés 21040 Date d'inscription jeudi 23 janvier 2003 Statut Modérateur Dernière intervention 21 août 2019 - 4 févr. 2014 à 14:34

Cette discussion concerne un article du site. Pour la consulter dans son contexte d'origine, cliquez sur le lien ci-dessous.

https://codes-sources.commentcamarche.net/source/100395-compter-les-bits-non-nuls-banal

BruNews Messages postés 21040 Date d'inscription jeudi 23 janvier 2003 Statut Modérateur Dernière intervention 21 août 2019
Modifié par BunoCS le 4/02/2014 à 15:49

Salut,
j'ai fait un test (mode GUI Windows), une dialog avec bouton A et B.

CODE C complet (à part ASM):

#include <windows.h>

#define ALIGN16   __declspec(align(16))
#define MEMDISPO  (MEM_COMMIT | MEM_RESERVE)
#define ONEPAGE   4096
#define mcVirtualAlloc(N) VirtualAlloc(0, N, MEMDISPO, PAGE_READWRITE);
#define mcVirtualFree(Addr) VirtualFree(Addr, 0, MEM_RELEASE);

#include "resource.h"
//#include "bnSSE.h"

#define NB      15625000    // 1000000000 / 64
#define NBSIZE  (NB * 8)    // 125000000 OCTETS !!!

typedef struct _BNDT {
  DWORD (*pfunc) (UINT64);
  HWND hstT;
  HWND hstR;
} BNDT, *PBNDT;

////    DEPUIS  bnCRT.asm     ////////////////////
char* bnultoa(DWORD dwnum, char* szdst);
void bnFillRndNbsize(void *pdst);
////      bnCRT.asm     ////////////////////

ALIGN16 DWORD DWRNDMUL[4] = {214013,214013,214013,214013};
ALIGN16 DWORD DWRNDADD[4] = {2531011,2531011,2531011,2531011};

BNDT bdt[2] = {0};
UINT64 *pUQW = 0;

DWORD PopA64(UINT64 k)
{
  int i;
  DWORD n = 0;
  for(i = 0; i < 64; i++) if(k & (1ll << i)) n++;
  return n;
}

DWORD PopA64bn(UINT64 k)
{
  return (DWORD) __popcnt64(k);
}

DWORD Count64(DWORD (*pfunc64) (UINT64))
{
  DWORD s, n;
  s = 0;
  for(n = 0; n < NB; ++n) s += pfunc64(pUQW[n]);
  return s;
}

void tstCount64(DWORD idx)
{
  char buf[24];
  UINT64 deb, fin;
  DWORD n;
  PBNDT pbn = &bdt[idx];
  deb = __rdtsc();
  n = Count64(pbn->pfunc);
  fin = __rdtsc();
  fin -= deb;
  *bnultoa((DWORD) fin, buf) = 0;
  SetWindowText(pbn->hstT, buf);
  *bnultoa(n, buf) = 0;
  SetWindowText(pbn->hstR, buf);
}

INT_PTR AppDlgProc(HWND hdlg, UINT mssg, WPARAM wParam, LPARAM lParam)
{
  switch(mssg) {
    case WM_INITDIALOG:
      SetClassLongPtr(hdlg, GCLP_HICON, (LONG_PTR) LoadIcon(0, IDI_APPLICATION));
      bdt[0].hstT = GetDlgItem(hdlg, IDST_TA);
      bdt[0].hstR = GetDlgItem(hdlg, IDST_A);
      bdt[1].hstT = GetDlgItem(hdlg, IDST_TB);
      bdt[1].hstR = GetDlgItem(hdlg, IDST_B);
      bdt[0].pfunc = PopA64;
      bdt[1].pfunc = PopA64bn;
      return 1;
    case WM_COMMAND:
      switch(LOWORD(wParam)) {
        case IDBT_A:
        case IDBT_B:
          tstCount64((DWORD) (LOWORD(wParam) - IDBT_A));
          return 0;
        case IDCANCEL: EndDialog(hdlg, 0);
      }
  }
  return 0;
}

void __fastcall myWinMain()
{
  pUQW = mcVirtualAlloc(NBSIZE);
  if(pUQW == 0) goto progEND;
  bnFillRndNbsize(pUQW);
  DialogBoxParam(GetModuleHandle(0), MAKEINTRESOURCE(IDD_APP), 0, AppDlgProc, 0);
  mcVirtualFree(pUQW);
progEND:
  ExitProcess(0);
}

-----------------
EXE x64 fait 2688 octets (2.62 Ko).

RESULTAT:
Retour n identique pour les 2 fonctions, IMPEC.
Les temps:
Bouton A (TON code) : 570240399 ticks.
BOUTON B (CPU code) : 77899931 ticks.

Conclusion:
Tant que faire se peut, toujours utiliser ce que fournit un CPU.
Tout autre code est quasi toujours une nuisance comparé au CPU.

BruNews Messages postés 21040 Date d'inscription jeudi 23 janvier 2003 Statut Modérateur Dernière intervention 21 août 2019
Modifié par BruNews le 4/02/2014 à 10:32

J'ai remarqué que MS VS Express 2013 charge kernel32.dll.
Existe-t-il un équivalent 64 bits "kernel64.dll" ?

Je suppose que tu veux dire "à l'exécution".
'VS' est un "IDE", il ne "charge" donc rien du tout, quand l'exe est lancé il n'y a plus notion de VS. C'est le loader system qui charge kernel32 car tout prog en est dépendant, si exe est compilé x64 alors c'est bien entendu un kernel32 x64 qui est chargé. Un exe x64 ne chargera QUE des DLLs x64, idem pour les vieilleries 32 qui ne chargeront que des 32 bits.

William VOIROL Messages postés 261 Date d'inscription mardi 12 décembre 2006 Statut Membre Dernière intervention 10 juin 2019
3 févr. 2014 à 09:08

Bonjour
Merci pour votre information.
Que faire pour que le problème soit pris en considération ?

Bonne journée également

cs_Le Pivert Messages postés 7903 Date d'inscription jeudi 13 septembre 2007 Statut Contributeur Dernière intervention 11 mars 2024 137
3 févr. 2014 à 08:39

Bonjour,

J'ai eu le même problème pour enregistrer le zip. Voir ceci:

http://codes-sources.commentcamarche.net/forum/affich-10016759-deposer-une-source

Le problème n'a pas été résolu depuis!

Bonne journée

William VOIROL Messages postés 261 Date d'inscription mardi 12 décembre 2006 Statut Membre Dernière intervention 10 juin 2019
3 févr. 2014 à 07:39

Mon intention n'est pas de faire ici un "snippet".
Mais je n'arrive pas à insérer le zip (5 ko).
Après avoir désigné le fichier zip en question, et cliqué sur "Charger", les 5 points défilent "éternellement" et on me demande si je veux ouvrir ou enregistrer "save.json" !?!

Pour y remédier, je donne ici le contenu du fichier Pop.cpp:


#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define NB 1000000000
uint64_t V64[NB/64];
uint8_t T8[256],T16[65536];

//×× PopA: comptage ×××××××××××××××××××××××××××××××××××××××××××××
int PopA8(uint8_t k) {
  int n=0;
  for(int i=0; i<8; i++) if(k&(1<<i)) ++n;
  return n;
}
int PopA16(uint16_t k) {
  int n=0;
  for(int i=0; i<16; i++) if(k&(1<<i)) ++n;
  return n;
}
int PopA32(uint32_t k) {
  int n=0;
  for(int i=0; i<32; i++) if(k&(1<<i)) ++n;
  return n;
}
int PopA64(uint64_t k) {
  int n=0;
  for(int i=0; i<64; i++) if(k&(1ll<<i)) ++n;
  return n;
}
//×× PopB: autre comptage ×××××××××××××××××××××××××××××××××××××××
int PopB8(uint8_t k) {
  int n=0;
  do n+=k&1; while(k>>=1);
  return n;
}
int PopB16(uint16_t k) {
  int n=0;
  do n+=k&1; while(k>>=1);
  return n;
}
int PopB32(uint32_t k) {
  int n=0;
  do n+=k&1; while(k>>=1);
  return n;
}
int PopB64(uint64_t k) {
  int n=0;
  do n+=k&1; while(k>>=1);
  return n;
}
//×× PopC: comptage pour population éparse ××××××××××××××××××××××
int PopC8(uint8_t k) {
  int n=0;
  while(k) {++n; k&=k-1;}
  return n;
}
int PopC16(uint16_t k) {
  int n=0;
  while(k) {++n; k&=k-1;}
  return n;
}
int PopC32(uint32_t k) {
  int n=0;
  while(k) {++n; k&=k-1;}
  return n;
}
int PopC64(uint64_t k) {
  int n=0;
  while(k) {++n; k&=k-1;}
  return n;
}
//×× PopD: addition par groupes ×××××××××××××××××××××××××××××××××
int PopD8(uint8_t k) {
  k=(k&0X55)+((k>>1)&0X55);
  k=(k&0X33)+((k>>2)&0X33);
  return (k&0X0F)+(k>>4);
}
int PopD16(uint16_t k) {
  k-=(k>>1)&0X5555;
  k=(k&0X3333)+((k>>2)&0X3333);
  k=(k&0X0F0F)+((k>>4)&0X0F0F);
  return (k&0X00FF)+(k>>8);
}
int PopD32(uint32_t k) {
  k=(k&0X55555555)+((k>>1)&0X55555555);
  k=(k&0X33333333)+((k>>2)&0X33333333);
  k=(k&0X0F0F0F0F)+((k>>4)&0X0F0F0F0F);
  k=(k&0X00FF00FF)+((k>>8)&0X00FF00FF);
  return (k&0X0000FFFF)+(k>>16);
}
int PopD64(uint64_t k) {
  k=(k&0X5555555555555555)+((k>> 1)&0X5555555555555555);
  k=(k&0X3333333333333333)+((k>> 2)&0X3333333333333333);
  k=(k&0X0F0F0F0F0F0F0F0F)+((k>> 4)&0X0F0F0F0F0F0F0F0F);
  k=(k&0X00FF00FF00FF00FF)+((k>> 8)&0X00FF00FF00FF00FF);
  k=(k&0X0000FFFF0000FFFF)+((k>>16)&0X0000FFFF0000FFFF);
  return (k&0X00000000FFFFFFFF)+(k>>32);
}
//×× PopE: addition par groupes bis ×××××××××××××××××××××××××××××××××
int PopE8(uint8_t kk) {
  uint32_t k=kk;
  k-=(k>>1)&0X55;
  k=(k&0X33)+((k>>2)&0X33);
  return (k+(k>>4))&0X0F;
}
int PopE16(uint16_t kk) {
  uint32_t k=kk;
  k-=(k>>1)&0X5555;
  k=(k&0X3333)+((k>>2)&0X3333);
  k=(k+(k>>4))&0X0F0F;
  return (k+(k>>8))&0X0000001F;
}
//×× PopF: addition par groupes optimisé ×××××××××××××××××××××××××××××××××
int PopF8(uint8_t kk) {
  uint32_t k=kk;
  k-=(k>>1)&0X55;
  k=(k&0X33)+((k>>2)&0X33);
  return (k+(k>>4))&0X0F;
}
int PopF16(uint16_t kk) {
  uint32_t k=kk;
  k-=(k>>1)&0X5555;
  k=(k&0X3333)+((k>>2)&0X3333);
  k=(k+(k>>4))&0X0F0F;
  return (k+(k>>8))&0X001F;
}
int PopF32(uint32_t k) {
  k-=(k>>1)&0X55555555;
  k=(k&0X33333333)+((k>>2)&0X33333333);
  k=(k+(k>>4))&0X0F0F0F0F;
  k+=(k>>8);
  return (k+(k>>16))&0X0000003F;
}
int PopF64(uint64_t k) {
  k-=(k>>1)&0X5555555555555555;
  k=(k&0X3333333333333333)+((k>>2)&0X3333333333333333);
  k=(k+(k>>4))&0X0F0F0F0F0F0F0F0F;
  k+=(k>>8);
  k+=(k>>16);
  return (k+(k>>32))&0X0000007F;
}
//×× PopG: multiplication ×××××××××××××××××××××××××××××××××××××
int PopG16(uint16_t kk) {
  uint32_t k=kk,n=(k>>1)&0X7777;
  k-=n;
  n=(n>>1)&0X7777;
  k-=n;
  n=(n>>1)&0X7777;
  k-=n;
  k=(k+(k>>4))&0X0F0F;
  return ((k*0X0101)>>8)&0X1F;
}
int PopG32(uint32_t k) {
  uint32_t n=(k>>1)&0X77777777;
  k-=n;
  n=(n>>1)&0X77777777;
  k-=n;
  n=(n>>1)&0X77777777;
  k-=n;
  k=(k+(k>>4))&0X0F0F0F0F;
  return (k*0X01010101)>>24;
}
int PopG64(uint64_t k) {
  uint64_t n=(k>>1)&0X7777777777777777;
  k-=n;
  n=(n>>1)&0X7777777777777777;
  k-=n;
  n=(n>>1)&0X7777777777777777;
  k-=n;
  k=(k+(k>>4))&0X0F0F0F0F0F0F0F0F;
  return (k*0X0101010101010101)>>56;
}
//×× PopH: addition et multiplication ×××××××××××××××××××××××××××××××××
int PopH16(uint16_t kk) {
  uint32_t k=kk;
  k-=(k>>1)&0X5555;
  k=(k&0X3333)+((k>>2)&0X3333);
  k=(k+(k>>4))&0X0F0F;
  return ((k*0X0101)>>8)&0X1F;
}
int PopH32(uint32_t k) {
  k-=(k>>1)&0X55555555;
  k=(k&0X33333333)+((k>>2)&0X33333333);
  k=(k+(k>>4))&0X0F0F0F0F;
  return (k*0X01010101)>>24;
}
int PopH64(uint64_t k) {
  k-=(k>>1)&0X5555555555555555;
  k=(k&0X3333333333333333)+((k>>2)&0X3333333333333333);
  k=(k+(k>>4))&0X0F0F0F0F0F0F0F0F;
  return (k*0X0101010101010101)>>56;
}
//×× PopI: 256 bytes précomptés ×××××××××××××××××××××××××××××××××××××
inline int PopI8(uint8_t k) { return T8[k]; }
inline int PopI16(uint16_t k) { return T8[k&0XFF]+T8[k>>8]; }
inline int PopI32(uint32_t k) {
  return T8[k&0XFF]+T8[(k>>8)&0XFF]+T8[(k>>16)&0XFF]+T8[k>>24];
}
inline int PopI64(uint64_t k) {
  return T8[k&0XFF]+T8[(k>>8)&0XFF]+T8[(k>>16)&0XFF]+T8[(k>>24)&0XFF]
    +T8[(k>>32)&0XFF]+T8[(k>>40)&0XFF]+T8[(k>>48)&0XFF]+T8[k>>56];
}
//×× PopJ: 65536 shorts précomptés ××××××××××××××××××××××××××××××
inline int PopJ16(uint16_t k) {return T16[k];}
inline int PopJ32(uint32_t k) {return (T16[k&0XFFFF]+T16[k>>16]);}
inline int PopJ64(uint64_t k) {
  return T16[k&0XFFFF]+T16[(k>>16)&0XFFFF]+T16[(k>>32)&0XFFFF]+T16[k>>48];
}
//×× Fonctions communes ××××××××××××××××××××××××××××××××××××××××××××××
void Count8(int(*F8)(uint8_t)) {
  clock_t t=clock();
  uint8_t *v8=(uint8_t*)&V64;
  uint32_t s=0;
  for(uint32_t n=0; n<NB/8; ++n) s+=F8(v8[n]);
  printf("   8 Bits: s=%u, t=%u ms\n",s,clock()-t);
}
void Count16(int(*F16)(uint16_t)) {
  clock_t t=clock();
  uint16_t *v16=(uint16_t*)&V64;
  uint32_t s=0;
  for(uint32_t n=0; n<NB/16; ++n) s+=F16(v16[n]);
  printf("  16 Bits: s=%u, t=%u ms\n",s,clock()-t);
}
void Count32(int(*F32)(uint32_t)) {
  clock_t t=clock();
  uint32_t *v32=(uint32_t*)&V64;
  uint32_t s=0;
  for(uint32_t n=0; n<NB/32; ++n) s+=F32(v32[n]);
  printf("  32 Bits: s=%u, t=%u ms\n",s,clock()-t);
}
void Count64(int(*F64)(uint64_t)) {
  clock_t t=clock();
  uint32_t s=0;
  for(uint32_t n=0; n<NB/64; ++n) s+=F64(V64[n]);
  printf("  64 Bits: s=%u, t=%u ms\n",s,clock()-t);
}
//×× main ××××××××××××××××××××××××××××××××××××××××××××××××××××××××××××
int main() {
  uint64_t m=0XFFFF;
  for(uint32_t i=0; i<NB/64; i+=2) { // "array" de 1 millard de bits
    V64[i]=rand()&m|((rand()&m)<<16)|((rand()&m)<<32)|((rand()&m)<<48);
    V64[i+1]=~V64[i];
  }
  for(uint32_t i=0; i<256; ++i) T8[i]=PopD8(i); // précomptage
  for(uint32_t i=0; i<65536; ++i) T16[i]=PopD16(i); // précomptage

  printf("Temps utilisé pour compter 1 miliard de bits\n\n");
  printf("PopA: comptage\n");
  Count8(PopA8); Count16(PopA16); Count32(PopA32); Count64(PopA64);
  printf("PopB: autre comptage\n");
  Count8(PopB8); Count16(PopB16); Count32(PopB32); Count64(PopB64);
  printf("PopC: comptage pour population éparse\n");
  Count8(PopC8); Count16(PopC16); Count32(PopC32); Count64(PopC64);
  printf("PopD: addition par groupes\n");
  Count8(PopD8); Count16(PopD16); Count32(PopD32); Count64(PopD64);
  printf("PopE: addition par groupes bis\n");
  Count8(PopE8); Count16(PopE16);
  printf("PopF: addition par groupes optimisé\n");
  Count8(PopF8); Count16(PopF16);  Count32(PopF32); Count64(PopF64);
  printf("PopG: multiplication\n");
  Count16(PopG16); Count32(PopG32); Count64(PopG64);
  printf("PopH: addition et multiplication\n");
  Count16(PopH16); Count32(PopH32); Count64(PopH64);
  printf("PopI: 256 bytes précomptés\n");
  Count8(PopI8); Count16(PopI16); Count32(PopI32); Count64(PopI64);
  printf("PopJ: 65536 shorts précomptés\n");
  Count16(PopJ16); Count32(PopJ32); Count64(PopJ64);
  getchar();
  return 0;
}

Encore toutes mes excuses.

Discussions similaires

Urgent Problème magento

compter le nombre de caractères d'un TextBox

Gestion des point de fidélité sous magento admin

Fonction pour compter le nombre de caractere d'une string

Mettre des bits dans un tableau ?

Votre réponse

Discussions similaires