Нахождение высшего порядка 1 в примитиве Java

Question

Мне нужно найти высший порядок 1 в некоторых длинных, целых и коротких шрифтах в Java. Например, если у меня был символ, который выглядел как 00110101, мне нужен метод, который будет возвращать 2 (индекс высшего порядка 1).

Теперь я знаю, что вы можете сделать это с помощью цикла for, например:

for(int i=0; i<8; i++)
    if((x & 1<<i) != 0) return i;
return -1;

но это намного медленнее, чем я хочу сделать. Я знаю, что у современных процессоров есть инструкции, которые делают это на чипе, поэтому я хочу знать, как я могу сделать вызов, а не иметь явный цикл.

РЕДАКТИРОВАТЬ: Бонусные баллы, если вы можете просто вернуть индексы всех из тех в примитиве.

Спасибо.

Answer 1

Integer.numberOfLeadingZeros(i) + 1

Этот метод использует хороший подход типа «разделяй и властвуй», скопированный здесь для вашего обзора:

public static int numberOfLeadingZeros(int i) {
    // HD, Figure 5-6
    if (i == 0)
        return 32;
    int n = 1;
    if (i >>> 16 == 0) { n += 16; i <<= 16; }
    if (i >>> 24 == 0) { n +=  8; i <<=  8; }
    if (i >>> 28 == 0) { n +=  4; i <<=  4; }
    if (i >>> 30 == 0) { n +=  2; i <<=  2; }
    n -= i >>> 31;
    return n;
}

Answer 2

На странице " Bit Twiddling Hacks " содержится множество битовых хаков. Один из них - найти индекс старшего бита .

Answer 3

Понятия не имею, быстрее ли это. Но у него нет петли.

if(i==0) return -1;

highest=0;
if (i & 0xffff0000)
{
   highest+=16;
   i>>=16;
}
if (i & 0xff00)
{
   highest+=8;
   i>>=8;
}
if (i & 0xf0)
{
   highest+=4;
   i>>=4;
}
if (i & 0xC)
{
   highest+=2;
   i>>=2;
}
if (i & 0x2)
{
   highest+=1;
}

return highest;

Answer 4

Java компилируется в независимый от платформы байт-код, вы не можете ожидать поддержки инструкций процессора. В противном случае ваш код или Integer.highestOneBit () должен быть настолько быстрым, насколько это возможно.

Answer 5

Насколько я могу судить, у Pentium и его друзей нет готовой инструкции для этого. Поэтому нужно использовать приличный алгоритм.

Ключом к быстрому получению ответа является использование бинарного поиска. Вы смотрите на long с 64 битами? 6 сравнений каждый раз дадут вам самый высокий бит.

Код работает для большого уродливого дерева из 64 операторов if, но только часть из них когда-либо будет выполнена, поэтому время выполнения хорошо.

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

Answer 6

Я не знаю, как выполнить команду CPU, но я знаю, что это будет намного быстрее, если вы развернете цикл и будете использовать явную битовую маскировку.

Кроме того, символ не 8 бит ... Я думаю, вы могли иметь в виду байт.