В стандартных библиотеках С++ я нашел только метод журнала с плавающей запятой. Теперь я использую журнал, чтобы найти уровень индекса в двоичном дереве (floor(2log(index))).
Код (С++):
int targetlevel = int(log(index)/log(2));
Я боюсь, что для некоторых элементов edge (элементы со значением 2 ^ n) log вернет n-1.999999999999 вместо n.0. Правильно ли этот страх? Как я могу изменить свое утверждение так, чтобы оно всегда возвращало правильный ответ?
Вместо этого вы можете использовать этот метод:
int targetlevel = 0;
while (index >>= 1) ++targetlevel;
Примечание: это изменит индекс. Если вам это нужно без изменений, создайте еще один временный int.
Угловой случай, когда индекс равен 0. Вероятно, вы должны проверить его отдельно и выбросить исключение или вернуть ошибку, если index == 0.
Если вы находитесь на платформе x86 или x86-64 на недавнем уровне, и вы, вероятно, используете ее, используйте команду bsr, которая вернет позицию самого старшего бита в целое число без знака. Оказывается, это точно так же, как log2(). Вот короткая функция C или С++, которая вызывает bsr с помощью встроенного ASM:
#include <stdint.h>
static inline uint32_t log2(const uint32_t x) {
uint32_t y;
asm ( "\tbsr %1, %0\n"
: "=r"(y)
: "r" (x)
);
return y;
}
Если вам нужна операция быстрого целочисленного журнала 2, следующая функция mylog2() сделает это, не беспокоясь о точности с плавающей запятой:
#include <limits.h>
static unsigned int mylog2 (unsigned int val) {
if (val == 0) return UINT_MAX;
if (val == 1) return 0;
unsigned int ret = 0;
while (val > 1) {
val >>= 1;
ret++;
}
return ret;
}
#include <stdio.h>
int main (void) {
for (unsigned int i = 0; i < 20; i++)
printf ("%u -> %u\n", i, mylog2(i));
putchar ('\n');
for (unsigned int i = 0; i < 10; i++)
printf ("%u -> %u\n", i+UINT_MAX-9, mylog2(i+UINT_MAX-9));
return 0;
}
В приведенном выше коде также есть небольшая тестовая проводка, чтобы вы могли проверить поведение:
0 -> 4294967295
1 -> 0
2 -> 1
3 -> 1
4 -> 2
5 -> 2
6 -> 2
7 -> 2
8 -> 3
9 -> 3
10 -> 3
11 -> 3
12 -> 3
13 -> 3
14 -> 3
15 -> 3
16 -> 4
17 -> 4
18 -> 4
19 -> 4
4294967286 -> 31
4294967287 -> 31
4294967288 -> 31
4294967289 -> 31
4294967290 -> 31
4294967291 -> 31
4294967292 -> 31
4294967293 -> 31
4294967294 -> 31
4294967295 -> 31
Он вернет UINT_MAX для входного значения 0 в качестве индикатора результата undefined, так что что-то, что вы должны проверить (недействительное целое число без знака будет иметь высокий логарифм).
Кстати, есть некоторые безумно быстрые хаки, чтобы сделать именно это (найти самый старший бит, установленный в 2-х дополнении), доступный из здесь. Я бы не предложил использовать их, если бы скорость не была самой существенной (я предпочитаю читаемость самостоятельно), но вы должны знать, что они существуют.
Вот что я делаю для 64-разрядных целых чисел без знака. Это вычисляет пол логарифма базы-2, что эквивалентно индексу самого значимого бита. Этот метод является курьезно быстрым для больших чисел, поскольку он использует развернутый цикл, который выполняется всегда в log₂64 = 6 шагов.
По существу, то, что он делает, вычитает постепенно меньшие квадраты в последовательности {0 ≤ k ≤ 5: 2 ^ (2 ^ k)} = {2³², 2¹⁶, 2⁸, 2⁴, 2², 2¹} = {4294967296, 65536, 256, 16, 4, 2, 1} и суммирует показатели k вычитаемых значений.
int uint64_log2(uint64_t n)
{
#define S(k) if (n >= (UINT64_C(1) << k)) { i += k; n >>= k; }
int i = -(n == 0); S(32); S(16); S(8); S(4); S(2); S(1); return i;
#undef S
}
Обратите внимание, что это возвращает -1, если задан недопустимый ввод 0 (это то, что проверяет начальный -(n == 0)). Если вы никогда не ожидаете вызвать его с помощью n == 0, вы можете подставить int i = 0; для инициализатора и добавить assert(n != 0); при входе в функцию.
Локарифмы целочисленного значения Base-10 можно вычислить аналогичным образом - с наибольшим квадратом для теста будет 10¹⁶, поскольку log₁₀2⁶⁴ ≅ 19.2659...
int uint64_log10(uint64_t n)
{
#define S(k, m) if (n >= UINT64_C(m)) { i += k; n /= UINT64_C(m); }
int i = -(n == 0);
S(16,10000000000000000); S(8,100000000); S(4,10000); S(2,100); S(1,10);
return i;
#undef S
}
Это было предложено в комментариях выше. Использование встроенных gcc:
static inline int log2i(int x) {
assert(x > 0);
return sizeof(int) * 8 - __builtin_clz(x) - 1;
}
static void test_log2i(void) {
assert_se(log2i(1) == 0);
assert_se(log2i(2) == 1);
assert_se(log2i(3) == 1);
assert_se(log2i(4) == 2);
assert_se(log2i(32) == 5);
assert_se(log2i(33) == 5);
assert_se(log2i(63) == 5);
assert_se(log2i(INT_MAX) == sizeof(int)*8-2);
}
У меня никогда не было проблем с точностью с плавающей запятой по формуле, которую вы используете (и быстрая проверка чисел от 1 до 2 31 - 1 не нашла ошибок), но если вы беспокоитесь, вы можете использовать эту функцию вместо этого, которая возвращает те же результаты и примерно на 66% быстрее в моих тестах:
int HighestBit(int i){
if(i == 0)
return -1;
int bit = 31;
if((i & 0xFFFFFF00) == 0){
i <<= 24;
bit = 7;
}else if((i & 0xFFFF0000) == 0){
i <<= 16;
bit = 15;
}else if((i & 0xFF000000) == 0){
i <<= 8;
bit = 23;
}
if((i & 0xF0000000) == 0){
i <<= 4;
bit -= 4;
}
while((i & 0x80000000) == 0){
i <<= 1;
bit--;
}
return bit;
}
int targetIndex = floor(log(i + 0.5)/log(2.0));
Это не стандартно или обязательно переносимо, но оно будет работать в целом. Я не знаю, насколько он эффективен.
Преобразование целочисленного индекса в число с плавающей запятой достаточной точности. Представление будет точным, если предположить, что точность достаточна.
Посмотрите на представление чисел с плавающей запятой IEEE, извлеките экспоненту и выполните необходимую настройку, чтобы найти журнал базы 2.
Есть аналогичные ответы выше. Этот ответ
Функции:
static int floorLog2(int64_t x)
{
assert(x > 0);
return 63 - __builtin_clzl(x);
}
static int ceilLog2(int64_t x)
{
if (x == 1)
// On my system __builtin_clzl(0) returns 63. 64 would make more sense
// and would be more consistent. According to stackoverflow this result
// can get even stranger and you should just avoid __builtin_clzl(0).
return 0;
else
return floorLog2(x-1) + 1;
}
Тестовый код:
for (int i = 1; i < 35; i++)
std::cout<<"floorLog2("<<i<<") = "<<floorLog2(i)
<<", ceilLog2("<<i<<") = "<<ceilLog2(i)<<std::endl;
Эта функция определяет, сколько бит требуется для представления числового интервала: [0..maxvalue].
unsigned binary_depth( unsigned maxvalue )
{
int depth=0;
while ( maxvalue ) maxvalue>>=1, depth++;
return depth;
}
Вычитая 1 из результата, вы получите floor(log2(x)), что является точным представлением log2(x), когда x является степенью 2.
x y y-1
0 0 -1
1 1 0
2 2 1
3 2 1
4 3 2
5 3 2
6 3 2
7 3 2
8 4 3
Если вы используете С++ 11, вы можете сделать это функцией constexpr:
constexpr std::uint32_t log2(std::uint32_t n)
{
return (n > 1) ? 1 + log2(n >> 1) : 0;
}
Насколько глубоко вы проектируете свое дерево? Вы можете установить диапазон значений... +/- 0,00000001 на число, чтобы заставить его целое значение.
На самом деле я не уверен, что вы нажмете число, например 1.99999999, потому что ваш лог2 не должен терять точность при вычислении значений 2 ^ n (так как число с плавающей точкой округляется до ближайшей мощности 2).
Эта функция я написал здесь
// The 'i' is for int, there is a log2 for double in stdclib
inline unsigned int log2i( unsigned int x )
{
unsigned int log2Val = 0 ;
// Count push off bits to right until 0
// 101 => 10 => 1 => 0
// which means hibit was 3rd bit, its value is 2^3
while( x>>=1 ) log2Val++; // div by 2 until find log2. log_2(63)=5.97, so
// take that as 5, (this is a traditional integer function!)
// eg x=63 (111111), log2Val=5 (last one isn't counted by the while loop)
return log2Val ;
}
Это старый пост, но я разделяю один алгоритм:
unsigned uintlog2(unsigned x)
{
unsigned l;
for(l=0; x>1; x>>=1, l++);
return l;
}
Перепишите ответ Тодда Лемана, чтобы он был более общим:
#include <climits>
template<typename N>
constexpr N ilog2(N n) {
N i = 0;
for (N k = sizeof(N) * CHAR_BIT; 0 < (k /= 2);) {
if (n >= static_cast<N>(1) << k) { i += k; n >>= k; }
}
return i;
}
Clang с -O3 разворачивает цикл:
0000000100000f50 pushq %rbp
0000000100000f51 movq %rsp, %rbp
0000000100000f54 xorl %eax, %eax
0000000100000f56 cmpl $0xffff, %edi
0000000100000f5c setg %al
0000000100000f5f shll $0x4, %eax
0000000100000f62 movl %eax, %ecx
0000000100000f64 sarl %cl, %edi
0000000100000f66 xorl %edx, %edx
0000000100000f68 cmpl $0xff, %edi
0000000100000f6e setg %dl
0000000100000f71 leal (,%rdx,8), %ecx
0000000100000f78 sarl %cl, %edi
0000000100000f7a leal (%rax,%rdx,8), %eax
0000000100000f7d xorl %edx, %edx
0000000100000f7f cmpl $0xf, %edi
0000000100000f82 setg %dl
0000000100000f85 leal (,%rdx,4), %ecx
0000000100000f8c sarl %cl, %edi
0000000100000f8e leal (%rax,%rdx,4), %eax
0000000100000f91 xorl %edx, %edx
0000000100000f93 cmpl $0x3, %edi
0000000100000f96 setg %dl
0000000100000f99 leal (%rdx,%rdx), %ecx
0000000100000f9c sarl %cl, %edi
0000000100000f9e leal (%rax,%rdx,2), %ecx
0000000100000fa1 xorl %eax, %eax
0000000100000fa3 cmpl $0x1, %edi
0000000100000fa6 setg %al
0000000100000fa9 orl %ecx, %eax
0000000100000fab popq %rbp
Когда n постоянно, результат вычисляется во время компиляции.
Учитывая то, как работают числа с плавающей запятой (грубо, мантисса * 2 ^ экспонента), тогда любое число до 2 ^ 127, которое является степенью 2, будет точно представлено без ошибок.
Это дает тривиальное, но довольно хакерское решение - интерпретировать битовую комбинацию числа с плавающей запятой как целое число и просто посмотреть на показатель степени. Это решение Дэвида Торнли выше.
float f = 1;
for (int i = 0; i < 128; i++)
{
int x = (*(int*)(&f)>>23) - 127;
int l = int(log(f) / log(2));
printf("i = %d, log = %d, f = %f quick = %d\n",
i, l, f, x);
f *= 2;
}
Неверно, что любое целое число может быть представлено как число с плавающей запятой - только те, у которых меньше битов, чем у мантиссы. В 32-битных числах, это стоит 23 бита.