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

10 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
Patrick Philippot
Clive wrote:
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



Ou bien tester la parité de l'entier avec Mod et recommencer 8 fois
après une division entière par 2 (shift de 1 à droite). Mais je doute
que cela soit plus rapide.

Ancien programmeur APL, je ne regrette absolument rien :-)).

--
Patrick Philippot - Microsoft MVP
MainSoft Consulting Services
www.mainsoft.fr
Avatar
Clive
Merci pour la réponse.
En effet je doute que cela soit plus rapide (mais on ne sait jamais).

Je vois que tu es un ancien d'IBM, donc l'APL c'était de l'IBM - pas
top, moi c'était sur un 68000 (Wicat) avec APL*PLUS

Clive
Avatar
Patrice Henrio
Sans tester, en aveugle et pour le fun d'un ancien LISPIEN qui le regrette

Function SommeBits(N as Integer) as integer
If N=0 then
SommeBits=0
else
SommeBits=(N mod 2) + SommeBits(N2)



End Function

La dernière division est une divisieon entière

Salut



"Clive" a écrit dans le message de news:

Merci pour la réponse.
En effet je doute que cela soit plus rapide (mais on ne sait jamais).

Je vois que tu es un ancien d'IBM, donc l'APL c'était de l'IBM - pas
top, moi c'était sur un 68000 (Wicat) avec APL*PLUS

Clive
Avatar
Clive
Merci Patrice,
Un bel exemple de la recursivité en prime.

Clive
Avatar
Patrice Henrio
En récursivité terminale qui plus est, puisque l'écriture

SommeBits(N)=SommeBits(N2)+ N mod 2

serait plus longue à exécuter à cause des la mise en pile qui n'est pas
nécessaire dans l'autre écriture.


"Clive" a écrit dans le message de news:

Merci Patrice,
Un bel exemple de la recursivité en prime.

Clive
Avatar
Patrick Philippot
Patrice Henrio wrote:
En récursivité terminale qui plus est, puisque l'écriture

SommeBits(N)=SommeBits(N2)+ N mod 2



Ah, on sent bien la culture Lisp. Vous n'auriez pas fait du ML / SML par
hasard?

Je sors d'un projet où nous avons utilisé SML .Net, la version .Net de
ML. J'avoue que j'ai un peu de mal à me faire à cette forme de pensée
(pour faire un peu de provoc, je dois dire que nous avons finalement
tout porté en C#, ça marche aussi bien, c'est plus facile à déboguer et
ça va des zillions de fois plus vite :-)) ).

--
Patrick Philippot - Microsoft MVP
MainSoft Consulting Services
www.mainsoft.fr
Avatar
Patrice Henrio
"Patrick Philippot" a écrit dans le
message de news:
Patrice Henrio wrote:
En récursivité terminale qui plus est, puisque l'écriture

SommeBits(N)=SommeBits(N2)+ N mod 2



Ah, on sent bien la culture Lisp. Vous n'auriez pas fait du ML / SML par
hasard?

Je sors d'un projet où nous avons utilisé SML .Net, la version .Net de ML.
J'avoue que j'ai un peu de mal à me faire à cette forme de pensée (pour
faire un peu de provoc, je dois dire que nous avons finalement tout porté
en C#, ça marche aussi bien, c'est plus facile à déboguer et ça va des
zillions de fois plus vite :-)) ).

--
Patrick Philippot - Microsoft MVP
MainSoft Consulting Services
www.mainsoft.fr



Je me mettrai au C (j'avoue que j'ai déjà essayé trois fois) quand on aura
compris que la rapidité du code ne doit pas être lié à "l'absconsité" du
fichier source.
A bas i++ quand i=i+1 est plus parlant et même je préfère i:=i+1 pour ne pas
confondre avec un test.
Je n'ai jamais fait de ML/SML.
Dans ma formation je me suis intéressé aux différents paradigmes de
programmation : procédural (pascal, basic, Forth ...), fonctionnel (LISP,
Schème), Objet (SmallTalk) et logique (Prolog).
Ma préférence va à la programmation fonctionnelle, même si à l'époque
SmallTalk m'avait beaucoup impressionné.
Mais le fait de passer d'un type de programmation à un autre est très
instructif et permet d'aborder un même problème sous différent point de vue.
Tout problème peut être traité dans n'importe lequel des paradigmes, le plus
souvent la difficulté de l'un par rapport à l'autre n'est lié qu'à nos
habitudes de pensées.

Pour le fonctionnel : considérez tout programme comme une boîte noire
traduit par une fonction (un peu comme un e touche de calculatrice), on
entre les données en paramètres et on récupère le résultat en sortie. Le
seul point embêtant c'est que les interfaces clients ne relèvent pas de ce
schéma de pensée ce qui impose "les effets de bord" : lors d'une impression
le résultat est physiquement ce qui est écrit à l'écran mais mentalement il
n'y a pas de résultat, or une fonction doit toujours renvoyer un résultat
qui puisse être utilisé par la fonction suivante (la composition de
fonctions remplace la succession d'actions du procédural) donc on définit la
fonction print(S) comme renvoyant S après avoir programmé à l'intérieur de
cette fonction un écho de S sur l'écran..
Avatar
Jean-Marc
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:

' version récursive
Private Function CompteBits(n As Long)
If n <= 0 Then
CompteBits = 0
Else
CompteBits = (n Mod 2) + CompteBits(n 2)
End If
End Function

' version linéaire
Private Function CompteBits1(n As Long)
Dim r As Integer

Do
r = r + (n Mod 2)
n = n / 2
Loop Until n = 0
CompteBits1 = r
End Function

Pas de surprises: la version linéaire est 11.5 fois plus
rapide que la version récursive, pour des raisons évidentes.

Cependant, l'important ici est le très bon algo de Patrick.

--
Jean-marc
"There are only 10 kind of people
those who understand binary and those who don't."
mailto: remove '_no_spam_' ;







"Patrice Henrio" a écrit dans le message de
news:
En récursivité terminale qui plus est, puisque l'écriture

SommeBits(N)=SommeBits(N2)+ N mod 2

serait plus longue à exécuter à cause des la mise en pile qui n'est pas
nécessaire dans l'autre écriture.


"Clive" a écrit dans le message de news:

Merci Patrice,
Un bel exemple de la recursivité en prime.

Clive




Avatar
Jean-Marc
"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 !

--
Jean-marc
"There are only 10 kind of people
those who understand binary and those who don't."
mailto: remove '_no_spam_' ;
Avatar
Zoury
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 :
'***
' Module
Option Explicit

Public Sub Main()

Dim bc As BitCounter
Dim i As Integer

Set bc = New BitCounter

Debug.Print "Byte"
Debug.Print Hex$(CByte(0)) & " -> " & bc.GetWordBitCount(0)
Debug.Print Hex$(CByte(255)) & " -> " & bc.GetWordBitCount(255)
Debug.Print

Debug.Print "Word"
Debug.Print Hex$(CInt(-32768)) & " -> " & bc.GetWordBitCount(-32768)
Debug.Print Hex$(CInt(32767)) & " -> " & bc.GetWordBitCount(32767)
Debug.Print Hex$(CInt(0)) & " -> " & bc.GetWordBitCount(0)
Debug.Print Hex$(CInt(1)) & " -> " & bc.GetWordBitCount(1)
Debug.Print Hex$(CInt(-1)) & " -> " & bc.GetWordBitCount(-1)
Debug.Print

Debug.Print "DWord"
Debug.Print Hex$(CLng(-2147483648#)) & " -> " &
bc.GetDWordBitCount(-2147483648#)
Debug.Print Hex$(CLng(2147483647)) & " -> " &
bc.GetDWordBitCount(2147483647)
Debug.Print Hex$(CLng(0)) & " -> " & bc.GetDWordBitCount(0)
Debug.Print Hex$(CLng(1)) & " -> " & bc.GetDWordBitCount(1)
Debug.Print Hex$(CLng(-1)) & " -> " & bc.GetDWordBitCount(-1)

End Sub
'***
' Classe BitCounter
Option Explicit

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
1 2