Jak zjistit počet bitů? – C / C++ – Fórum – Programujte.com

Dá se nějak efektivně vypočítat počet nulových bitů v čísle zleva? Aniž by člověk musel používat smyčky a převody pomocí *char. Existuje na to nějaký trik? V tabulce níže jsou uvedené číselné rozsahy, lichý řádek minimum, sudý maximum. Jde o 32 bitové číslo, ale pro jednoduchost jsem ty nuly nedopsal.  Tak např. první dva řádky mají mít 30 nul zleva. Jako další příklad uvedu uint32_t x=0b100010 ... číslo se nachází ve druhém rozsahu a má mít 26 nul. Jaksi mě zajímá jestli existuje nějaká finta jak vrátit řád ve kterém se to nachází.

                      10  0x02        0
                      10  0x02        0
                    1000  0x08        1
                    1000  0x08        1
                  100000  0x20        2
                  100110  0x26        2
                10000000  0x80        3
                10011011  0x9B        3
              1000000000  0x200       4
              1001101111  0x26F       4
            100000000000  0x800       5
            100110111111  0x9BF       5
          10000000000000  0x2000      6
          10011011111111  0x26FF      6
        1000000000000000  0x8000      7
        1001101111111111  0x9BFF      7
      100000000000000000  0x20000     8
      100110111111111111  0x26FFF     8
    10000000000000000000  0x80000000  9
    10011011111111111111  0x9BFFF     9    
  1000000000000000000000  0x200000    10
  1001101111111111111111  0x26FFFF    10
100000000000000000000000  0x800000    11
100110111111111111111111  0x9BFFFF    11

A na co to potřebuju. Abych nemusel procházet celkem 15 rozsahů pomocí podmínek if ..else .. tak že bych prostě spočítal počet nul.

Proc pomoci if else? Mame prece bitovy posun a cyklus.

Jestli tě správně chápu, tak logaritmus je tvůj kamarád  . 

#include <stdio.h>
#include <math.h>
#include <limits.h>

const intSize = CHAR_BIT * sizeof(int);

int main(void) {
	int cislo = 1020;

	int result = intSize - (int)log2(cislo);

	printf("%d\n", result);
	return 0;
}

#2 KIIV
cyklus se mu asi nebude líbit   . A rekurze mu nebude dost efektivní. Pak bude každá rada drahá.   

hu

#3 PiranhaGreg
Dík, myslím že tu funguje, ale že to tiskne výsledek o jedna větší:

int cislo = 0b10;

dává 31, a mělo by být 30. Tak asi výsledek zmenšit o jedna.

A napadla mě ještě další možnost, delší kód, ale možná (?) efektivnější, vytvořit 16 podmínek if .. else, kde každá testuje danou proměnnou s maskou. Takže test na první masku by byl třeba takto:

( cislo & ~0x11111111111111111111111111111100 )

přičemž by to mělo zjišťovat jestli se zam nachází 30 nul vlevo a další dva bity nerozhodují.

Pak udělat další podmnku a posunout o dva bity

( cislo & ~0x11111111111111111111111111110000 )

ale toto dělám nejspíš špatně páč to nefunguje.

Nejrychlejší je použít asm instrukci bsr, která je k tomu určená :).

A to by bylo složité? O asm nic nevím, neumím

Stačí volat funkci 

int __builtin_clz (unsigned int x)

Returns the number of leading 0-bits in x, starting at the most significant bit position. If x is 0, the result is undefined.

Ale je to pouze pro gcc... Upřímně řešíš kraviny ;-). 

 Třeba tohle (pro VS).

int cislo = 12345;
int bitCount = 0;

__asm
  {
    mov eax, cislo;
    bsr eax, eax;
    mov bitCount, eax;
  }

Tak jo, ta instrukce je skvělá. Smyčka 4000x4000 trvala 0.03s, logarismus trvá 0.35s

Vím že řeším kraviny, ale radši použiju tu rychlejší variantu přeci jen. Díky všem

#9 Satik
To mi hází

error: expected '(' before '{' token|

Není třeba něco includovat?

Koukni se na příklad použití ;-).

#11 oxidián
To byl asm kód pro Visual Studio, musíš si zjistit, jak se asm zapisuje pro tvůj kompilátor.

Jinak to Gregovo řešení s největší pravděpodobností právě používá tu instrukci, takže to nemusíš řešit přes asm ;) 

Já nemám VS a píšu v C. VS ani nenainstaluju. Pokud to nejde do C tak asi nemá smysl abych se na to díval.

"Mixing C and asm code" hledej pro tvůj překladač. Nedávno ses tu vytahoval, jak umíš používat Google, tak ho použij!!

hu

Zatím mi to ale stačí, dík