Logo GNT
Actualités Tests & Guides Bons Plans
GTA 6 iPhone 17 Copilot Switch 2 Temu ChatGPT Tesla
OVH Cloud OVH Cloud
Entraide Développement Développement Visual Basic Sommer les bits d'un variable ?

Sommer les bits d'un variable ?

17 réponses
Avatar
Clive
Bonjour TLM,

Pour les besoins de mon logiciel de Sudoku, j'ai besoin de "compter"
les bits d'un entier (je stocke des possibilit=E9s de 0 =E0 511 sur le 9
premiers bits d'un entier).
Je sais le faire avec un boucle et un AND dans le style :
I =3D 0 TO 8; If (2^I) AND MonInteger then Bits=3DBits+1
Mais je me demande s'il n'y a pas un moyen plus rapide (ou plus
=E9l=E9gant) de le faire. (Ancien programmeur APL, je regrette l'absence
de ce genre de manipulation de vecteurs dans VB).

Des id=E9es svp ?

Merci d'avance

Clive
Signaler un problème avec ce contenu

7 réponses

Supprimer
Cette action est irreversible, confirmez la suppression du commentaire ?
Signaler le commentaire

Veuillez sélectionner un problème

Nudité
Violence
Harcèlement
Fraude
Vente illégale
Discours haineux
Terrorisme
Autre
1 2
Avatar
Zoury
> Private m_nCount As Long





Private m_nLookupByte() As Long

Private Sub Class_Initialize()

Dim v As Variant
Dim i As Long
ReDim m_nLookupByte(0 To 255) As Long

' tableau de valeurs précalculées
v = Array(0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4, 1, 2, 2, 3,


2,
3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, _
1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 2, 3, 3, 4,


3,
4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, _
1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 2, 3, 3, 4,


3,
4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, _
2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5,


4,
5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, _
1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 2, 3, 3, 4,


3,
4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, _
2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5,


4,
5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, _
2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5,


4,
5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, _
3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 4, 5, 5, 6,


5,
6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8)

' on le copie dans un tableau fortement typé..
' je sais.. j'suis maniaque.. ;O)
For i = 0 To 255
m_nLookupByte(i) = v(i)
Next

End Sub

Public Function GetByteBitCount(ByVal b As Byte) As Long
GetByteBitCount = m_nLookupByte(b)
End Function

Public Function GetWordBitCount(ByVal w As Integer) As Long
GetWordBitCount = GetByteBitCount(HIBYTE(w)) +
GetByteBitCount(LOBYTE(w))
End Function

Public Function GetDWordBitCount(ByVal dw As Long) As Long
GetDWordBitCount = GetWordBitCount(HIWORD(dw)) +
GetWordBitCount(LOWORD(dw))
End Function

Private Function HIBYTE(ByVal w As Integer) As Byte
HIBYTE = (w And &HFF00&) &H100&
End Function

Private Function LOBYTE(ByVal w As Integer) As Byte
LOBYTE = w And &HFF&
End Function

Private Function HIWORD(ByVal dw As Long) As Integer
HIWORD = (dw And &HFFFF0000) &H10000
End Function

Private Function LOWORD(ByVal dw As Long) As Integer
If (dw And &H8000&) Then
LOWORD = dw Or &HFFFF0000
Else
LOWORD = dw And &HFFFF&
End If
End Function
'***

--
Cordialement
Yanick
MVP pour Visual Basic

"Clive" a écrit dans le message de
news:
Bonjour TLM,

Pour les besoins de mon logiciel de Sudoku, j'ai besoin de "compter"
les bits d'un entier (je stocke des possibilités de 0 à 511 sur le 9
premiers bits d'un entier).
Je sais le faire avec un boucle et un AND dans le style :
I = 0 TO 8; If (2^I) AND MonInteger then Bits=Bits+1
Mais je me demande s'il n'y a pas un moyen plus rapide (ou plus
élégant) de le faire. (Ancien programmeur APL, je regrette l'absence
de ce genre de manipulation de vecteurs dans VB).

Des idées svp ?

Merci d'avance

Clive




Avatar
Zoury
le courriel est parti tout seul...

j'allais dire que cet attribut est totalement inutilisé, et donc, tout
aussi totalement inutile. :O)
> Private m_nCount As Long


Avatar
Clive Lumb
Zoury wrote:
Salut Clive ! :O)

Dans un autre ordre d'idée, tu pourrais te faire une "lookup table"
(valeurs précalculées).. j'imagine que c'est plus rapide à la longue

ex :


<SNIP>

Hello Yannick !
Solution intéressante - je vais voir ce que cela donne en vitesse d'éxe.
Pour l'instant ce projet est en Standby - vacances obligent - mais dès que
je reviens à la prog je te dirai.

A plus
Clive
Avatar
Zoury
Bonjour ! :O)

Cette version devrait être un tout petit peu plus rapide ;O) :
'**
Private Function CompteBits(ByVal n As Long) As Long

Do
CompteBits = CompteBits + (n And 1)
n = n 2
Loop Until n = 0

End Function
'**
Le seul problème avec cet algo, c'est qu'il ne gère pas les nombre négatif.
Il retourne des résultats erronés.


Voici les résultats d'un benchmark comparant trois façons de faire :
'***
Option Explicit

'Résultats :

' IDE
'Nombre de tours : 1000000
'Temps de la boucle : 6 ms
'GetByteBitCount : 393 ms
'GetWordBitCount : 1794 ms
'GetDWordBitCount : 5096 ms
'GetWordBitCount2 : 1364 ms
'GetDWordBitCount2 : 1425 ms
'GetBitCount (Byte val) : 579 ms
'GetBitCount (Word val) : 823 ms
'GetBitCount (DWord val) : 1353 ms

' EXE
'Nombre de tours : 1000000
'Temps de la boucle : 1 ms
'GetByteBitCount : 78 ms
'GetWordBitCount : 175 ms
'GetDWordBitCount : 390 ms
'GetWordBitCount2 : 740 ms
'GetDWordBitCount2 : 718 ms
'GetBitCount (Byte val) : 75 ms
'GetBitCount (Word val) : 82 ms
'GetBitCount (DWord val) : 98 ms

Public Sub Main()

Const NUM_LOOP As Long = 1000000
Dim nLoop As Long
Dim i As Long
Dim n As Long
Dim sw As CStopWatch
Dim bc As BitCounter

Dim nBCByte As Long
Dim nBCWord As Long
Dim nBCDWord As Long
Dim nBCWord2 As Long
Dim nBCDWord2 As Long
Dim nBCByte3 As Long
Dim nBCWord3 As Long
Dim nBCDWord3 As Long

Set sw = New CStopWatch
Set bc = New BitCounter

Call sw.Reset
For i = 1 To NUM_LOOP
Next
nLoop = sw.Elapsed

Call sw.Reset
For i = 1 To NUM_LOOP
n = bc.GetByteBitCount(&H7F)
Next
nBCByte = sw.Elapsed

Call sw.Reset
For i = 1 To NUM_LOOP
n = bc.GetWordBitCount(&H7FFF)
Next
nBCWord = sw.Elapsed

Call sw.Reset
For i = 1 To NUM_LOOP
n = bc.GetDWordBitCount(&H7FFFFFFF)
Next
nBCDWord = sw.Elapsed

Call sw.Reset
For i = 1 To NUM_LOOP
n = bc.GetWordBitCount2(&H7FFF)
Next
nBCWord2 = sw.Elapsed

Call sw.Reset
For i = 1 To NUM_LOOP
n = bc.GetDWordBitCount2(&H7FFFFFFF)
Next
nBCDWord2 = sw.Elapsed

Call sw.Reset
For i = 1 To NUM_LOOP
n = bc.GetBitCount(&H7F)
Next
nBCByte3 = sw.Elapsed

Call sw.Reset
For i = 1 To NUM_LOOP
n = bc.GetBitCount(&H7FFF)
Next
nBCWord3 = sw.Elapsed

Call sw.Reset
For i = 1 To NUM_LOOP
n = bc.GetBitCount(&H7FFFFFFF)
Next
nBCDWord3 = sw.Elapsed

Dim s As String
s = "Nombre de tours : " & NUM_LOOP & vbNewLine & _
"Temps de la boucle : " & nLoop & " ms" & vbNewLine & _
"GetByteBitCount : " & nBCByte - nLoop & " ms" & vbNewLine & _
"GetWordBitCount : " & nBCWord - nLoop & " ms" & vbNewLine & _
"GetDWordBitCount : " & nBCDWord - nLoop & " ms" & vbNewLine & _
"GetWordBitCount2 : " & nBCWord2 - nLoop & " ms" & vbNewLine & _
"GetDWordBitCount2 : " & nBCDWord2 - nLoop & " ms" & vbNewLine & _
"GetBitCount (Byte val) : " & nBCByte3 - nLoop & " ms" & vbNewLine &
_
"GetBitCount (Word val) : " & nBCWord3 - nLoop & " ms" & vbNewLine &
_
"GetBitCount (DWord val) : " & nBCDWord3 - nLoop & " ms"
Call MsgBox(s)

End Sub
'***
Option Explicit

Private Declare Sub CopyMemory _
Lib "kernel32" _
Alias "RtlMoveMemory" ( _
ByRef pDst As Any, _
ByRef pSrc As Any, _
ByVal ByteLen As Long)

Private m_nLookupByte() As Long

Private Sub Class_Initialize()

Dim v As Variant
Dim i As Long
ReDim m_nLookupByte(0 To 255) As Long

' tableau de valeur précalculer
v = Array(0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4, 1, 2, 2, 3, 2,
3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, _
1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 2, 3, 3, 4, 3,
4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, _
1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 2, 3, 3, 4, 3,
4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, _
2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4,
5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, _
1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 2, 3, 3, 4, 3,
4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, _
2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4,
5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, _
2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4,
5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, _
3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 4, 5, 5, 6, 5,
6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8)

' on le copie dans un tableau fortement typé..
For i = 0 To 255
m_nLookupByte(i) = v(i)
Next

End Sub

Public Function GetByteBitCount(ByVal b As Byte) As Long
GetByteBitCount = m_nLookupByte(b)
End Function

Public Function GetWordBitCount(ByVal w As Integer) As Long
GetWordBitCount = GetByteBitCount(HIBYTE(w)) +
GetByteBitCount(LOBYTE(w))
End Function

Public Function GetDWordBitCount(ByVal dw As Long) As Long
GetDWordBitCount = GetWordBitCount(HIWORD(dw)) +
GetWordBitCount(LOWORD(dw))
End Function

Public Function GetWordBitCount2(ByVal w As Integer) As Long

Dim bt(1) As Byte

Call CopyMemory(bt(0), w, 2)
GetWordBitCount2 = m_nLookupByte(bt(0)) + _
m_nLookupByte(bt(1))

End Function

Public Function GetDWordBitCount2(ByVal dw As Long) As Long

Dim bt(3) As Byte

Call CopyMemory(bt(0), dw, 4)
GetDWordBitCount2 = m_nLookupByte(bt(0)) + _
m_nLookupByte(bt(1)) + _
m_nLookupByte(bt(2)) + _
m_nLookupByte(bt(3))

End Function

' exact pour les nombres positifs seulement..
Public Function GetBitCount(ByVal n As Long) As Long

Do
GetBitCount = GetBitCount + (n And 1)
n = n &H10
Loop Until n = 0

End Function

Private Function HIBYTE(ByVal w As Integer) As Byte
HIBYTE = (w And &HFF00&) &H100&
End Function

Private Function LOBYTE(ByVal w As Integer) As Byte
LOBYTE = w And &HFF&
End Function

Private Function HIWORD(ByVal dw As Long) As Integer
HIWORD = (dw And &HFFFF0000) &H10000
End Function

Private Function LOWORD(ByVal dw As Long) As Integer
If (dw And &H8000&) Then
LOWORD = dw Or &HFFFF0000
Else
LOWORD = dw And &HFFFF&
End If
End Function
'***

On constate que pour les nombres positifs, l'ago de Patrice est très
puissant :O)

--
Cordialement
Yanick
MVP pour Visual Basic
Avatar
Zoury
Afin de mettre en pratique le tutoriel de Jean-Marc (merci encore :O)
http://membres.lycos.fr/jeanmarcn/cvb/cetvb.htm


Le code n'est pas de moi (vous l'aurez surement deviné... :O/), mais il
s'agit, théoriquement, de la manière la plus rapide de calculer les bits
d'un nombre sur 32 bits. Ça ne demande que 17 operations ASM.


Voici le code en C (en asm en fait..) :
//***
#define export __declspec (dllexport)

export int __stdcall GetBitCount(const int n);

int __stdcall GetBitCount(const int n)
{

__asm
{
// input in EAX
MOV EAX, n;
// counting bits
MOV EDX, EAX;
SHR EAX, 1;
AND EAX, 0x055555555;
SUB EDX, EAX;
MOV EAX, EDX;
SHR EDX, 2;
AND EAX, 0x033333333;
AND EDX, 0x033333333;
Add EAX, EDX;
MOV EDX, EAX;
SHR EAX, 4;
Add EAX, EDX;
AND EAX, 0x00F0F0F0F;
IMUL EAX, 0x001010101;
SHR EAX, 24;
//result in EAX
MOV n, EAX;
}

return n;

}
//***


Il suffit d'ajouter le tout à la classe :
'***
Private Declare Function GetBitCountAPI _
Lib "...ReleaseBitCount.dll" _
Alias "" ( _
ByVal n As Long) As Long

Public Function GetBitCountC(ByVal n As Long) As Long
GetBitCountC = GetBitCountAPI(n)
End Function
'***

J'obtiens désormais les résultats suivant :
'***
Nombre de tours : 1000000
Temps de la boucle : 1 ms
GetByteBitCount : 78 ms
GetWordBitCount : 170 ms
GetDWordBitCount : 383 ms
GetWordBitCount2 : 728 ms
GetDWordBitCount2 : 724 ms
GetBitCount (Byte val) : 74 ms
GetBitCount (Word val) : 82 ms
GetBitCount (DWord val) : 99 ms
GetBitCountC (Byte val) : 99 ms
GetBitCountC (Word val) : 97 ms
GetBitCountC (DWord val) : 97 ms
'***

Les temps sont donc beaucoup plus proche des temps de l'algo de Patrice et
supporte les nombres négatifs en prime :O)

--
Cordialement
Yanick
MVP pour Visual Basic
Avatar
Zoury
grrr.. encore parti trop vite, je n'avais pas fini de préciser..

je disais donc :
Afin de mettre en pratique le tutoriel de Jean-Marc (merci encore :O)
http://membres.lycos.fr/jeanmarcn/cvb/cetvb.htm



J'ai ajouté une nouvelle fonction à la classe BitCounter.

Le code asssembleur n'est pas de moi (vous l'aurez surement deviné... :O/),
mais il
s'agirait, d'une des manières les plus rapides de calculer les bits
d'un nombre sur 32 bits (optimisé pour un processeur AMD Athlon x86).

L'algo de base ne demande que 15 operations assembleurs.

J'ai trouvé le code ici (j'avais déjà vu un algorithme semblable dans un
autre livre...) :
http://groups.google.com/groups?selm”4701548.40610%40news.bluegrass.net

--
Cordialement
Yanick
MVP pour Visual Basic
Avatar
pas-de-spam>Wanadoo.fr
Jean-Marc a écrit :
"Jean-Marc" a écrit dans le message de
news:42bdac95$0$13238$

Hello,

bien entendu, on n'oubliera pas qu'aucune implémentation
raisonnable n'utiliserait la récursivité dans ce contexte.
Pour la petite histoire, voici les 2 fonctions qui
implémentent le très bon algorithme de Patrick:



^^^^^^^
rede caesari qua est caesari:
je voilais dire l'algo de Patrice !




Bonjour,

Merci beaucoup pour le tutoriel !!
Voilà qui va être très utile !!

Depuis le temps que je galère avec les temps de traitement de DIB noir
et blanc, je va pouvoir l'écrire en C++ !!!

Merci beaucoup Jean Marc

Christophe
1 2