Я сейчас скажу глупость, но с высокой долей вероятности, лучше всего будут оптимизированы операции сдвига. Так что я бы писал сдвиг в цикле до обнуления результата. Количество разрядов определишь по счётчику. Думаю компилятор это классно оптимизирует и в машинном коде это будет летать :)

Может вы и правы, но «на компилятор надейся, а сам не плошай».

asm(«bsr %1, %0»:«=a»(bit):«b»(value));

На входе в value нужное число, на выходе в bit номер старшего бита. Работает только на x86/x86-64, зато более быстрого варианта нет.

http://web.itu.edu.tr/kesgin/mul06/intel/instr/bsf.html

ассемблер хорош, но мне нужно портабельное решение.

> http://web.itu.edu.tr/kesgin/mul06/intel/instr/bsf.html Не годиться, число 64-х битовое

>> http://web.itu.edu.tr/kesgin/mul06/intel/instr/bsf.html Не годиться, число 64-х битовое

Я интелловский ассемблер вообще не знаю, тыкнул пальцем в возможном направлении )

>Как на C/C++ быстро вычислить номер старшего бита 64-х битового числа

Кажись это http://aggregate.org/MAGIC/#Leading%20Zero%20Count

> Как на C/C++ быстро вычислить номер старшего бита 64-х битового числа.

Записывай: если ты считаешь биты с наименее значимого, то номер бита будет 64, а если с наиболее - то первый.


Если же тебе по какой-то странной случайности нужно значение бита, то:

uint64_t MASK = ~(~((uint64_t)0) >> 1);

if (var & MASK)
{
...

Оно! Спасибо.

>Оно! Спасибо.

OMG, так значит всем можно пользоваться, в том числе циклами, ты просто не знаешь битовые операции.

> вычислить номер старшего бита 64-х битового числа

63.

Если я правильно вас понял, вам нужно узнать номер старшего _установленного_ бита в числе. Насколько мне известно, нет хитрой битовой операции (типа как (x & -x) для младшего бита) для вашего запроса. Делайте в цикле битовый сдвиг или пользуйте ассемблерную вставку.

> Оно! Спасибо.
Это не оно. Это (x & (1 << 63)), то бишь 0 или (1 << 63), а вовсе не floor двоичного логарифма.

> надо быстро найти пол от двоичного логарифма

ты мне должен новое лицо и новую руку.

>Я сейчас скажу глупость, но с высокой долей вероятности

Действительно сказал глупость. У вероятностей нет долей, тем более высоких. Высоким может быть дом или дерево, а вероятность может быть большой.

Самый тупой способ:

uint64_t number;
...
int pow2 = 0;
while(number > 1){
  number >>= 1;
  pow2++;
}

А что такое «пол от двоичного логарифма»?

А вообще, приличные алгоритмы можно найти здесь

чёртов спортивный интересс

subj, вот набыдлокодил, ругайте :)

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

int
find(uint64_t digit, uint64_t mask, int median)
{
        uint64_t hi, lo;

        median >>= 1;

        if (median && (digit & mask)) {
                mask >>= median;
                hi = digit >> median;
                lo = digit & mask;

                if (hi)
                        return median + find(hi, mask, median);
                else
                        return find(lo, mask, median);
        }

        return 1;
}

int
main()
{
        uint64_t digit = 1ULL;;
        uint64_t mask = -1ULL;
        int n = 64;

        while (n-- > 0) {
                printf("%20llu: high bit # %d\n", digit, find(digit, mask, 64));
                digit <<= 1;
        }

        return 0;
}

> ругайте

> uint64_t

нет такого типа.

а у меня есть :)

grep uint64_t /usr/include/stdint.h

> а у меня есть :)

а ты кто? о_О я тебя не знаю. какова твоя причастность к С89/С99?

Если так придираться, то получится, что гарантированно 64-битного типа вообще нет.

> Если так придираться, то получится, что гарантированно 64-битного типа вообще нет.

молодец, возьми ништяк с полки ;)

но с другой стороны, с99 гарантирует наличие [эмуляции] 64+-битного целого.

Не гарантирует, он лишь гарантирует, что char <= short <= int <= long <= long long. А сколько где бит - пофиг. На пиках, вон, char и short == int8_t; int == int06_t; long == int32_t. В gcc на 32-битной int и long - одно и то же, а на 64-битной long 64-битный (вроде бы)...

Так что лучше не долбать себе и другим мозг, а пользоваться четко оговоренными типами, если нужна конкретная разрядность числа.

> Не гарантирует

гарантирует. с99 именно что __гарантирует__ наличие (u)int_least64_t. когда же ты уже ума наберёшься, задолбал тупить в техразделах…

grep -R int_least64_t /usr/include/|wc -l
48

Маловато будет. А тупить мне нравится. Может, я по жизни - баран? =)

> Может, я по жизни - баран?

ты не поверишь…

быстро вычислить номер старшего бита ...

http://graphics.stanford.edu/~seander/bithacks.html#IntegerLogObvious

там несколько алгоритмов для 32-х битных, а для 64-х битных можешь последовательно применить любые два на выбор :)

Кхм... man ffs, не?

> Не гарантирует, он лишь гарантирует, что char <= short <= int <= long <= long long

Вообще-то гарантирует. Пункт 7.18.1.1: ( текст скопирован из http://www.open-std.org/jtc1/sc22/WG14/www/docs/n1256.pdf )

The typedef name uintN_t designates an unsigned integer type with width N … if an implementation provides integer types with widths of 8, 16, 32, or 64 bits, no padding bits, and (for the signed types) that have a two’s complement representation, it shall define the corresponding typedef names.

То есть если такие типы существуют, то typedef должен быть. Если посмотреть в 7.18.1.2, то видим:

The following types are required: int_least8_t int_least16_t int_least32_t int_least64_t uint_least8_t uint_least16_t uint_least32_t uint_least64_t

Так что тип не короче 64 бит там требуется.

Та же фигня и с POSIX: http://pubs.opengroup.org/onlinepubs/9699919799/basedefs/stdint.h.html

А ещё можно поизвращаться так

#include <iostream>
#include <bitset>

#include <stdint.h>

using namespace std;

int main(int argc, char **argv)
{
	uint64_t val = 2;;
	bitset<64> bset(val);
	int i = bset.size() - 1;
	for(; i >= 0; --i)
		if(bset[i])
			break;
	if( -1 == i )
		cout << "No bits set" << endl;
	else
		cout << i << endl;
}

bit = var >> (sizeof (var) - 1);

> Вообще-то гарантирует. Пункт 7.18.1.1

...

То есть если такие типы существуют, то typedef должен быть.

Там не сказано, что «если такие типы существуют» (где?), а «если реализация обеспечивает». Причём по c99 не гарантируется наличие ни одного из этих типов, а posix не гарантирует наличие только 64-битных чисел и предлагает вызывать

getconf -a | grep POSIX_V7

Но можно ли себе представить такую реализацию, которая обеспечивала бы 8-, 16-, 32-битные числа, а также int_least64_t (который теоретически может быть, например, 128-битным), но не обеспечивала бы 64-битного числа? По-моему, это невероятно.

А вообще, gcc сейчас обеспечивает и 128-битные числа (__int128_t), в том числе на 32-разрядных системах.

>Не гарантирует, он лишь гарантирует, что char <= short <= int <= long <= long long. А сколько где бит - пофиг.

Бля, ну как уже достали регулярно появляющиеся в Development подобные высказывания. Cтандарт С99 _гарантирует_ минимально возможные размеры для этих типов, в частности long long _должен_ иметь не менее 64 бит (но может больше). Читайте 5.2.4.2.1 Sizes of integer types <limits.h> до просветления.

Самый быстрый способ - двоичный поиск на if-ах

а вообще ты можешь сделать свой класс, который сможет предоставлять хоть 1024 бит.

Тестировал сдвиг, в итоге примерно такой код работает в несколько раз быстрее, если верить valgrind. Только оформить должным образом...

size_t optimal_zalloc_size(size_t size)
{
	register size_t value = 0;

	if (size <= 0x10000) {
		if (size <= 0x100) {
			if (size <= 0x10) {
				/*if (size <= 0x8)
					value = 0x8;
				else
					value = 0x10;*/
				value = 0x10;

			} else {
				if (size <= 0x40)
					if (size <= 0x20)
						value = 0x20;
					else
						value = 0x40;
				else
					if (size <= 0x80)
						value = 0x80;
					else
						value = 0x100;
			}
		} else {
...

#include <strings.h>
int main()
{
    volatile unsigned long long x;

    return ffsll(x);
}

gcc -O3 --save-temps -m64:

main:
        movq    -24(%rsp), %rax
        movq    $-1, %rdx
        bsfq    %rax, %rax
        cmove   %rdx, %rax
        addq    $1, %rax
        ret

gcc сейчас обеспечивает и 128-битные числа (__int128_t), в том числе на 32-разрядных системах.

О, круто. не знал. Теперь можно хранить IPv6 адрес в одной целочисленной переменной.

В компиляторах, умеющих расширения GNU (а это отнюдь не только gcc), есть специальные встроенные функции, __builtin_clz

Есть такая книженция: Hacker's Delight, Henry S. Warren, Jr. (Алгоритмические трюки для программистов), а вней глава: 5.3. Подсчет ведущих нулевых битов (с. 86)

Очевидно, что номер старшего бита в 64-битовом числе — это 63. А вот старшего единичного бита — другой вопрос.

Черт, я слоупок.

> bit = var >> (sizeof (var) - 1);

sizeof ВНЕЗАПНО возвращает число байт..

> sizeof ВНЕЗАПНО возвращает число байт..

очепятался, конечно же sizeof(var)*8