Индекс бита самого низкоуровневого
У Вас есть прокси SOCKS? Если Вы имеете, Вы попытка caould FreeCap к socksify Ваше соединение мерзавца. Я использовал мерзавца этот путь некоторое время.
В противном случае все еще попытка FreeCap. IIRC это смогло использовать прокси HTTP, но я не попробовал это.
РЕДАКТИРОВАНИЕ: Я использование usualy socksify cmd.exe FreeCap и с тех пор (почти) все cmdline программы, которые я запускаю от той сессии, являюсь socksified также. Вот почему я рекомендовал Бесплатное Ограничение, так как SocksCap (другая альтернатива) не прокладывает себе путь.
Что касается использования http.proxy, это по некоторым причинам никогда не работало на меня с mingw версией и моими прокси HTTP компании.
9 ответов
У Intel есть специальные инструкции для поиска бита самого низкого или самого высокого порядка. BSF похоже на то, что вам нужно. что касается простого C, возможно, на странице бит-твидл-хаков есть то, что вам нужно.
По крайней мере, вы могли бы использовать таблицу полубайтов или байтов, чтобы ускорить процесс. Что-то вроде этого (продемонстрировано для int, но при необходимости легко заменяется на longlong).
/*
0000 - 0
0001 - 1
0010 - 2
0011 - 1
0100 - 3
0101 - 1
0110 - 2
0111 - 1
1000 - 4
1001 - 1
1010 - 2
1011 - 1
1100 - 3
1101 - 1
1110 - 2
1111 - 1
*/
int ffs(int i) {
int ret = 0;
int j = 0;
static const int _ffs_tab[] =
{ 0, 1, 2, 1, 3, 1, 2, 1, 4, 1, 2, 1, 3, 1, 2, 1 };
while((i != 0) && (ret == 0)) {
ret = _ffs_tab[i & 0x0f];
if(ret > 0) {
break;
}
i >>= 4;
j += 4;
/* technically the sign bit could stay, so we mask it out to be sure */
i &= INT_MAX;
}
if(ret != 0) {
ret += j;
}
return ret;
}
Самый быстрый, который я нашел, - это ffsll (long long) в string.h.
При использовании Visual Studio _BitScanForward :
Для gcc попробуйте __ builtin_ctz или __builtin_ffs :
Как всегда, следует обращаться к сгенерированному коду, чтобы убедиться, что генерируются правильные инструкции.
Вы можете изолировать самый младший установленный бит с помощью x & (~ x + 1) ; это дает вам наименьшее битовое значение, а не индекс (например, если x = 01101000, то результат будет 00001000). Самый быстрый способ добраться оттуда до индекса - это, вероятно, оператор switch:
switch(x & (~x + 1))
{
case 0ULL: index = -1; break;
case 1ULL: index = 0; break;
case 2ULL: index = 1; break;
case 4ULL: index = 2; break;
...
case 9223372036854775808ULL: index = 63; break;
}
Уродливый, но без цикла.
Как насчет этого? Это значительно уменьшает количество циклов.
int shifts = 0;
if ((bits & 0xFFFFFFFFFFFFULL) == 0) // not in bottom 48 bits
{
shifts = 48;
}
else if ((bits & 0xFFFFFFFFFFULL == 0) // not in bottom 40 bits
{
shifts = 40;
}
else
// etc
bits >>= shifts; // do all the shifts at once
// this will loop at most 8 times
for(i = 0;!(bits & 1ULL);i++)
bits >>= 1;
index = shifts + i;
Как насчет реализации своего рода двоичного поиска?
Посмотрите на младшие биты, полученные в результате побитовой обработки и значения маски, которое состоит из единиц в младшей половине. Если это значение равно нулю, вы знаете, что самый маленький бит находится в верхней половине числа.
в противном случае разрежьте его пополам и продолжайте снова.
This might work for 32 bits. Should be easy enough to extend to 64.
// all bits left of lsb become 1, lsb & right become 0
y = x ^ (-x);
// XOR a shifted copy recovers a single 1 in the lsb's location
u = y ^ (y >> 1);
// .. and isolate the bit in log2 of number of bits
i0 = (u & 0xAAAAAAAA) ? 1 : 0;
i1 = (u & 0xCCCCCCCC) ? 2 : 0;
i2 = (u & 0xF0F0F0F0) ? 4 : 0;
i3 = (u & 0xFF00FF00) ? 8 : 0;
i4 = (u & 0xFFFF0000) ? 16 : 0;
index = i4 | i3 | i2 | i1 | i0;
Obviously, if there is some way to have the hardware do it, i.e., if special CPU instructions are available, that is the way to go.
Я написал две функции, они возвращают тот же результат, что и ffsll ().
int func1( uint64_t n ){
if( n == 0 ) return 0;
n ^= n-1;
int i = 0;
if( n >= 1ull<<32 ){ n>>=32; i+=32; }
if( n >= 1ull<<16 ){ n>>=16; i+=16; }
if( n >= 1ull<< 8 ){ n>>= 8; i+= 8; }
if( n >= 1ull<< 4 ){ n>>= 4; i+= 4; }
if( n >= 1ull<< 2 ){ n>>= 2; i+= 2; }
if( n >= 1ull<< 1 ){ i+= 1; }
return i+1;
}
int func2( uint64_t n ){
return n? ((union ieee754_float)((float)(n^(n-1)))).ieee.exponent-126: 0;
}
Я не знаю, какая из них самая быстрая: ffsll (), func1 () или func2 () ?
вы можете вдвое уменьшить сложность вашего алгоритма, сначала проверяя, четное или нечетное ваше число. Если он четный, у вас младший бит - первый.
Для нечетных случаев вы можете реализовать такой двоичный поиск ...