Notifikationer

Markér alle som læst Log ud

Lasse Novice

30. juli 2004 - 18:19 Der er 18 kommentarer og
1 løsning

Position af bit

Hej alle sammen

Jeg har et lille problem ang. hastighed. Jeg har en integer, og i denne er der eet bit sat. Jeg vil gerne vide paa hvilken position bittet er sat.

Eks:

integer vaerdi|bit streng|position
1|1|1
4|100|3
64|1000000|7

Findes der en let funktion til dette, eller skal man goere noget a la:

int i = 1;
int search = 64;
while(true)
{
if(search == 1) break;
search = search >> 1;
i++;
}

Synes godt om

arne_v Ekspert

30. juli 2004 - 18:30 #1

Du har allerede en simpel løkke.

Jeg mener ikke at der er noget indbygget i .NET for dette.

Du kunne formentligt speede det marginalt op ved at lave en
binær søgning i.s.f. en sekventiel søgning (< 65536 så er det en af de laveste
16 bits der er sat, < 256 så er det en af de laveste 8 bits der er sat).

Synes godt om

arne_v Ekspert

30. juli 2004 - 18:59 #2

Det er noget hurtigere. Leg selv videre med:

using System;

class MainClass
{
public static int ffs1(uint v)
{
uint tmp = v;
for(int i = 1; i <= 32; i++)
{
if(tmp == 1) return i;
tmp >>= 1;
}
return -1;
}
public static int ffs2(uint v)
{
if(v < 0x00010000)
{
if(v < 0x00000100)
{
if(v < 0x00000010)
{
if(v < 0x00000004)
{
if(v < 0x00000002)
{
return 1;
}
else
{
return 2;
}
}
else
{
if(v < 0x00000008)
{
return 3;
}
else
{
return 4;
}
}
}
else
{
if(v < 0x00000040)
{
if(v < 0x00000020)
{
return 5;
}
else
{
return 6;
}
}
else
{
if(v < 0x00000080)
{
return 7;
}
else
{
return 8;
}
}
}
}
else
{
if(v < 0x00001000)
{
if(v < 0x00000400)
{
if(v < 0x00000200)
{
return 9;
}
else
{
return 10;
}
}
else
{
if(v < 0x00000800)
{
return 11;
}
else
{
return 12;
}
}
}
else
{
if(v < 0x00004000)
{
if(v < 0x00002000)
{
return 13;
}
else
{
return 14;
}
}
else
{
if(v < 0x00008000)
{
return 15;
}
else
{
return 16;
}
}
}
}
}
else
{
if(v < 0x01000000)
{
if(v < 0x00100000)
{
if(v < 0x00040000)
{
if(v < 0x00020000)
{
return 17;
}
else
{
return 18;
}
}
else
{
if(v < 0x00080000)
{
return 19;
}
else
{
return 20;
}
}
}
else
{
if(v < 0x00400000)
{
if(v < 0x00200000)
{
return 21;
}
else
{
return 22;
}
}
else
{
if(v < 0x00800000)
{
return 23;
}
else
{
return 24;
}
}
}
}
else
{
if(v < 0x10000000)
{
if(v < 0x04000000)
{
if(v < 0x02000000)
{
return 25;
}
else
{
return 26;
}
}
else
{
if(v < 0x08000000)
{
return 27;
}
else
{
return 28;
}
}
}
else
{
if(v < 0x40000000)
{
if(v < 0x20000000)
{
return 29;
}
else
{
return 30;
}
}
else
{
if(v < 0x80000000)
{
return 31;
}
else
{
return 32;
}
}
}
}
}
}
private const int N = 10000000;
public static void Main(string[] args)
{
for(int i = 0; i < 32; i++)
{
Console.WriteLine(ffs1((uint)(1 << i)) + " " + ffs2((uint)(1 << i)));
}
int res = 0;
long t1 = DateTime.Now.Ticks;
for(int i = 0; i < N; i++) {
res = ffs1(65536);
}
long t2 = DateTime.Now.Ticks;
Console.WriteLine(res + " : " + (t2 - t1));
long t3 = DateTime.Now.Ticks;
for(int i = 0; i < N; i++) {
res = ffs2(65536);
}
long t4 = DateTime.Now.Ticks;
Console.WriteLine(res + " : " + (t4 - t3));
}
}

Synes godt om

arne_v Ekspert

30. juli 2004 - 19:00 #3

Men det gør ikke koden mindre !

:-)

Synes godt om

arne_v Ekspert

30. juli 2004 - 19:00 #4

Og et svar såfremt ingen har bedre ideer.

Synes godt om

Lasse Novice

30. juli 2004 - 23:51 #5

ok, ja, jeg regnede heller ikke med at der var andre svar. Jeg havde haabet paa at der var noget nemt der kunne bruges og som fyldte en linie kode. Men nej....

Synes godt om

arne_v Ekspert

31. juli 2004 - 00:41 #6

Den der binære søgning er tilsyneladende den hurtigste.

Synes godt om

arne_v Ekspert

31. juli 2004 - 00:42 #7

using System;

class MainClass
{
public static int ffs1(uint v)
{
uint tmp = v;
for(int i = 1; i <= 32; i++)
{
if(tmp == 1) return i;
tmp >>= 1;
}
return -1;
}
public static int ffs2(uint v)
{
uint tmp = v;
if(tmp == 0)
{
return -1;
}
int i = 1;
while((tmp & 1) == 0)
{
tmp >>= 1;
i++;
}
return i;
}
private static int[] table = {
0,1,2,2,3,3,3,3,4,4,4,4,4,4,4,4,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,
6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,
7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,
7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,
8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,
8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,
8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,
8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8
};
public static int ffs3(uint v)
{
uint a, x;
x = (uint)(v & -v);
a = (uint)((x <= 0xFFFF) ? ((x <= 0xFF) ? 0 : 8) : ((x <= 0xFFFFFF) ? 16 : 24));
return (int)(table[x >> (int)a] + a);
}
public static int ffs4(uint v)
{
if(v < 0x00010000)
{
if(v < 0x00000100)
{
if(v < 0x00000010)
{
if(v < 0x00000004)
{
if(v < 0x00000002)
{
return 1;
}
else
{
return 2;
}
}
else
{
if(v < 0x00000008)
{
return 3;
}
else
{
return 4;
}
}
}
else
{
if(v < 0x00000040)
{
if(v < 0x00000020)
{
return 5;
}
else
{
return 6;
}
}
else
{
if(v < 0x00000080)
{
return 7;
}
else
{
return 8;
}
}
}
}
else
{
if(v < 0x00001000)
{
if(v < 0x00000400)
{
if(v < 0x00000200)
{
return 9;
}
else
{
return 10;
}
}
else
{
if(v < 0x00000800)
{
return 11;
}
else
{
return 12;
}
}
}
else
{
if(v < 0x00004000)
{
if(v < 0x00002000)
{
return 13;
}
else
{
return 14;
}
}
else
{
if(v < 0x00008000)
{
return 15;
}
else
{
return 16;
}
}
}
}
}
else
{
if(v < 0x01000000)
{
if(v < 0x00100000)
{
if(v < 0x00040000)
{
if(v < 0x00020000)
{
return 17;
}
else
{
return 18;
}
}
else
{
if(v < 0x00080000)
{
return 19;
}
else
{
return 20;
}
}
}
else
{
if(v < 0x00400000)
{
if(v < 0x00200000)
{
return 21;
}
else
{
return 22;
}
}
else
{
if(v < 0x00800000)
{
return 23;
}
else
{
return 24;
}
}
}
}
else
{
if(v < 0x10000000)
{
if(v < 0x04000000)
{
if(v < 0x02000000)
{
return 25;
}
else
{
return 26;
}
}
else
{
if(v < 0x08000000)
{
return 27;
}
else
{
return 28;
}
}
}
else
{
if(v < 0x40000000)
{
if(v < 0x20000000)
{
return 29;
}
else
{
return 30;
}
}
else
{
if(v < 0x80000000)
{
return 31;
}
else
{
return 32;
}
}
}
}
}
}
private const int N = 10000000;
public static void Main(string[] args)
{
for(int i = 0; i < 32; i++)
{
Console.WriteLine(ffs1((uint)(1 << i)) + " " +
ffs2((uint)(1 << i)) + " " +
ffs3((uint)(1 << i)) + " " +
ffs4((uint)(1 << i)));
}
int res = 0;
long t1 = DateTime.Now.Ticks;
for(int i = 0; i < N; i++) {
res = ffs1(65536);
}
long t2 = DateTime.Now.Ticks;
Console.WriteLine("alg 1 : " + (t2 - t1));
long t3 = DateTime.Now.Ticks;
for(int i = 0; i < N; i++) {
res = ffs2(65536);
}
long t4 = DateTime.Now.Ticks;
Console.WriteLine("alg 2 : " + (t4 - t3));
long t5 = DateTime.Now.Ticks;
for(int i = 0; i < N; i++) {
res = ffs3(65536);
}
long t6 = DateTime.Now.Ticks;
Console.WriteLine("alg 3 : " + (t6 - t5));
long t7 = DateTime.Now.Ticks;
for(int i = 0; i < N; i++) {
res = ffs4(65536);
}
long t8 = DateTime.Now.Ticks;
Console.WriteLine("alg 4 : " + (t8 - t7));
}
}

Synes godt om

arne_v Ekspert

31. juli 2004 - 00:42 #8

alg 1 : 8437500
alg 2 : 5156250
alg 3 : 2187500
alg 4 : 1250000

Synes godt om

Lasse Novice

02. august 2004 - 17:06 #9

excellente... jeg takker mange gange.

Synes godt om

Lasse Novice

04. august 2004 - 18:32 #10

Jeg har en anden loesning, har dog ikke checket hastigheden endnu:

System.COllections.Hashtable table = new ....

table.add(0, 0);
table.add(1, 1);
table.add(2, 2);
table.add(4, 3);
table.add(8, 4);
osv....

int bitnummerSat = (int)table[integervalueMedEtBitSat]

Synes godt om

arne_v Ekspert

04. august 2004 - 19:26 #11

Ideen er genial.

Implementeringen er la la.

Synes godt om

arne_v Ekspert

04. august 2004 - 19:26 #12

private static Hashtable htable = new Hashtable();
static MainClass()
{
for(int i = 0; i < 32; i++)
{
htable.Add((UInt32)(1 << i), (Int32)(i + 1));
}
}
public static int ffs5(uint v)
{
return (int)htable[v];
}

Synes godt om

arne_v Ekspert

04. august 2004 - 19:27 #13

alg 1 : 13719728
alg 2 : 8011520
alg 3 : 3204608
alg 4 : 2503600
alg 5 : 33648384
alg 6 : 400576

Synes godt om

arne_v Ekspert

04. august 2004 - 19:28 #14

Vi ser at alg 5 som er Hashtable er den langsomste af alle.

Men i en lettere ændret udgave alg 6 så er den faktisk suverænt
den hurtigste.

Synes godt om

arne_v Ekspert

04. august 2004 - 19:28 #15

private static int[] ztable = { -1, 1, 2, 27, 3, 24, 28, -1, 4, 17,
25, 31, 29, 12, -1, 14, 5, 8, 18, -1,
26, 23, 32, 16, 30, 11, 13, 7, -1, 22,
15, 10, 6, 21, 9, 20, 19 };
public static int ffs6(uint v)
{
return ztable[v % 37];;
}

Synes godt om

arne_v Ekspert

04. august 2004 - 19:29 #16

Hvis nogen ikke kan få tiderne til at stemme med de forrige, så det fordi
det her er på en langsommere maskine.

Synes godt om

arne_v Ekspert

04. august 2004 - 19:29 #17

Hele koden:

using System;
using System.Collections;

class MainClass
{
public static int ffs1(uint v)
{
uint tmp = v;
for(int i = 1; i <= 32; i++)
{
if(tmp == 1) return i;
tmp >>= 1;
}
return -1;
}
public static int ffs2(uint v)
{
uint tmp = v;
if(tmp == 0)
{
return -1;
}
int i = 1;
while((tmp & 1) == 0)
{
tmp >>= 1;
i++;
}
return i;
}
private static int[] table = {
0,1,2,2,3,3,3,3,4,4,4,4,4,4,4,4,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,
6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,
7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,
7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,
8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,
8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,
8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,
8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8
};
public static int ffs3(uint v)
{
uint a, x;
x = (uint)(v & -v);
a = (uint)((x <= 0xFFFF) ? ((x <= 0xFF) ? 0 : 8) : ((x <= 0xFFFFFF) ? 16 : 24));
return (int)(table[x >> (int)a] + a);
}
public static int ffs4(uint v)
{
if(v < 0x00010000)
{
if(v < 0x00000100)
{
if(v < 0x00000010)
{
if(v < 0x00000004)
{
if(v < 0x00000002)
{
return 1;
}
else
{
return 2;
}
}
else
{
if(v < 0x00000008)
{
return 3;
}
else
{
return 4;
}
}
}
else
{
if(v < 0x00000040)
{
if(v < 0x00000020)
{
return 5;
}
else
{
return 6;
}
}
else
{
if(v < 0x00000080)
{
return 7;
}
else
{
return 8;
}
}
}
}
else
{
if(v < 0x00001000)
{
if(v < 0x00000400)
{
if(v < 0x00000200)
{
return 9;
}
else
{
return 10;
}
}
else
{
if(v < 0x00000800)
{
return 11;
}
else
{
return 12;
}
}
}
else
{
if(v < 0x00004000)
{
if(v < 0x00002000)
{
return 13;
}
else
{
return 14;
}
}
else
{
if(v < 0x00008000)
{
return 15;
}
else
{
return 16;
}
}
}
}
}
else
{
if(v < 0x01000000)
{
if(v < 0x00100000)
{
if(v < 0x00040000)
{
if(v < 0x00020000)
{
return 17;
}
else
{
return 18;
}
}
else
{
if(v < 0x00080000)
{
return 19;
}
else
{
return 20;
}
}
}
else
{
if(v < 0x00400000)
{
if(v < 0x00200000)
{
return 21;
}
else
{
return 22;
}
}
else
{
if(v < 0x00800000)
{
return 23;
}
else
{
return 24;
}
}
}
}
else
{
if(v < 0x10000000)
{
if(v < 0x04000000)
{
if(v < 0x02000000)
{
return 25;
}
else
{
return 26;
}
}
else
{
if(v < 0x08000000)
{
return 27;
}
else
{
return 28;
}
}
}
else
{
if(v < 0x40000000)
{
if(v < 0x20000000)
{
return 29;
}
else
{
return 30;
}
}
else
{
if(v < 0x80000000)
{
return 31;
}
else
{
return 32;
}
}
}
}
}
}
private static Hashtable htable = new Hashtable();
static MainClass()
{
for(int i = 0; i < 32; i++)
{
htable.Add((UInt32)(1 << i), (Int32)(i + 1));
}
}
public static int ffs5(uint v)
{
return (int)htable[v];
}
private static int[] ztable = { -1, 1, 2, 27, 3, 24, 28, -1, 4, 17,
25, 31, 29, 12, -1, 14, 5, 8, 18, -1,
26, 23, 32, 16, 30, 11, 13, 7, -1, 22,
15, 10, 6, 21, 9, 20, 19 };
public static int ffs6(uint v)
{
return ztable[v % 37];;
}
private const int N = 10000000;
public static void Main(string[] args)
{
for(int i = 0; i < 32; i++)
{
Console.WriteLine(ffs1((uint)(1 << i)) + " " +
ffs2((uint)(1 << i)) + " " +
ffs3((uint)(1 << i)) + " " +
ffs4((uint)(1 << i)) + " " +
ffs5((uint)(1 << i)) + " " +
ffs6((uint)(1 << i)));
}
int res = 0;
long t1 = DateTime.Now.Ticks;
for(int i = 0; i < N; i++) {
res = ffs1(65536);
}
long t2 = DateTime.Now.Ticks;
Console.WriteLine("alg 1 : " + (t2 - t1));
long t3 = DateTime.Now.Ticks;
for(int i = 0; i < N; i++) {
res = ffs2(65536);
}
long t4 = DateTime.Now.Ticks;
Console.WriteLine("alg 2 : " + (t4 - t3));
long t5 = DateTime.Now.Ticks;
for(int i = 0; i < N; i++) {
res = ffs3(65536);
}
long t6 = DateTime.Now.Ticks;
Console.WriteLine("alg 3 : " + (t6 - t5));
long t7 = DateTime.Now.Ticks;
for(int i = 0; i < N; i++) {
res = ffs4(65536);
}
long t8 = DateTime.Now.Ticks;
Console.WriteLine("alg 4 : " + (t8 - t7));
long t9 = DateTime.Now.Ticks;
for(int i = 0; i < N; i++) {
res = ffs5(65536);
}
long t10 = DateTime.Now.Ticks;
Console.WriteLine("alg 5 : " + (t10 - t9));
long t11 = DateTime.Now.Ticks;
for(int i = 0; i < N; i++) {
res = ffs6(65536);
}
long t12 = DateTime.Now.Ticks;
Console.WriteLine("alg 6 : " + (t12 - t11));
}
}

Synes godt om

Lasse Novice

06. august 2004 - 22:25 #18

Hvordan kom du lige paa ffs6, er der evt en forklaring paa hvorfor og hvordan det virker?

Synes godt om

arne_v Ekspert

06. august 2004 - 22:39 #19

Ideen med hash er god. Hashtable har alt for meget overhead. Men jeg var
overbevist om at man kunne lave en "hurtig hashing" optimeret til lige
netop dette problem.

Det er meget normalt at bruge modulus til hashing, så jeg lavede et lille program
som fandt det mindste tal hvor 2^n % x gav forskellige tal for alle n=0..31,
det tal var 37 og så var det bare at konstruere et array som returnerede
korrekt bit numme rudfra % 37.

Synes godt om

Ny bruger Nybegynder

Din løsning...

Tilladte BB-code-tags: [b]fed[/b] [i]kursiv[/i] [u]understreget[/u] Web- og emailadresser omdannes automatisk til links. Der sættes "nofollow" på alle links.

Følg dette spørgsmål

Opret Preview

Se alle it-kurser fra Computerworld Kurser

IT-kurser om Microsoft 365, sikkerhed, personlig vækst, udvikling, digital markedsføring, grafisk design, SAP og forretningsanalyse.

Se alle it-kurser

Flere spørgsmål fra C# kategorien

Titel	Indlæg	Oprettet	Seneste aktivitet
Log i Azure Af joki i C#	1	04/12/202517:27	06/12/202520:32
Hent Virksomhed hos graphql.datafordeler.dk Af krukken i C#	13	18/11/202510:57	20/11/202508:59
Http client med X509Certificate2 Af joki i C#	6	11/09/202515:08	11/09/202518:51
pull request Af OBS i C#	1	30/08/202510:47	03/09/202518:51
Vejledning i god opbygning af program, erklæring af lister og modeller. Af Henrik_B i C#	10	10/04/202519:47	13/04/202502:40

Se alle spørgsmål i kategorien Opret spørgsmål

Log ind eller opret profil

Hov!

For at kunne deltage på Computerworld Eksperten skal du være logget ind.

Det er heldigvis nemt at oprette en bruger: Det tager to minutter og du kan vælge at bruge enten e-mail, Facebook eller Google som login.

Du kan også logge ind via nedenstående tjenester

Alle kategorier på Eksperten

Seneste artiklerRSS

07:52

To it-topchefer: Sådan sikrer du dine kompetencer i en tid, hvor AI presser it-folk til arbejdsløshed

07:07

Kan ændre iPhone-kameraet markant: Står foran sin største opgradering i årevis

06:00

Morgen-briefing: Meta åbner algoritmen for forældre / Børsnoteret dansk tech-selskab fordobler indtjeningen / Regering overvejer at dele AI-gevinster med befolkningen

09:03

Et kinesisk kampfly i frit fald - og en verden, som vi slet ikke ønsker os

13/05

Nedtælling til skæbnesvanger messe for Apple: Det kan du forvente fra det enorme WWDC-show

13/05

Han opfandt Oculus Rift og står nu bag vildt AI-baseret våbenfirma: Har fordoblet sin værdi på et år - er nu 400 milliarder kroner værd

13/05

Netcompany-stifterne André Rogaczewski og Claus Bo Jørgensen skovler penge ind: Så meget scorede de i 2025

13/05

BitLocker kan knækkes på få minutter med en USB-stick: Sådan kan du beskytte din pc

13/05

Kæmpe-strejke kan snart lamme Samsung: Forhandlinger brudt sammen - 50.000 medarbejdere vil nedlægge arbejdet

13/05

Har ikke andre muligheder: Danske universiteter nødt til at betale 64 millioner kroner til Oracle i ny licens-afgift

13/05

Alle CISO'er er ramt af dette paradoks: Jo bedre arbejdet udføres, jo mindre værdifuldt fremstår det

Vis flere artikler

IT-JOB

Jyske Bank

Engageret forretningsudvikler til Securities and Asset Management

Netcompany A/S

Managing Architect

Forsvarsministeriets Materiel- og Indkøbsstyrelse

Medarbejdere til arkitekturledelsesteam for styring af Strategisk Arkitekturforum og Arkitekturløsningsforum i Forsvaret

KMD A/S

Senior Test Consultant

Forsvarsministeriets Materiel- og Indkøbsstyrelse

Sektionschef til Enterprise Arkitektur i Forsvaret på Østerbro

Vis flere jobs

Seneste spørgsmål Seneste aktivitet

I går 23:24	Google sheets beregning udfra dato Af rickiegrayholm i Office & Kontorpakker
I går 18:09	Outlook Classic, lukker ikke Af mort1 i E-mail programmer
13/0520:48	Bred buet skærm vs. 2 skærme Af Nanarsi i Skærme
13/0518:07	Tilslut printer til netværk med WPS - hvis WPS slukkes på Router mistes forbindelse. Af Uvanga i Wifi
11/0521:05	Questyle M15i lydforstærker Af valby i Diverse

White papers

Undgå at printeren bliver svageste led i sikkerheden
Konica Minolta
Arctic Wolf Threat Report 2026: Sådan ændrer ransomware-landskabet sig
Arctic Wolf
Arctic Wolf Security Operations Report 2025: Indblik i moderne sikkerhedsdrift
Arctic Wolf
Erfaringer fra frontlinjen: Sådan ændrer trusselsbilledet sig
Arctic Wolf

Flere white papers »