Каков наиболее эффективный способ найти индекс самого левого / правого неустановленного бита в Java? - PullRequest
Новая
       10

Каков наиболее эффективный способ найти индекс самого левого / правого неустановленного бита в Java?

6 голосов
/ 27 июня 2011

Предположим, что у нас есть int x = 371, то есть в двоичном формате 101110011.Я хочу найти индекс самого левого неустановленного бита (в данном случае 7) и индекс самого правого неустановленного бита (в этом случае 2).Какой самый эффективный способ сделать это?

Вот что у меня есть: 

public class BitOperatons {

    public static int setBit(int x, int i) {
        int y = x | (1 << i);
        return y;
    }

    public static boolean isBitSet(int x, int i) {
        int y = setBit(0, i);
        return y == (x & y);
    }    

    public static int findLeftMostSetBit(int x) {
        for (int i = 31; i >= 0; i--) {
            if (isBitSet(x, i))
                return i;
        }
        return -1;
    }

    public static int findRightMostUnsetBit(int x) {
        for (int i = 0; i <= 31; i++) {
            if (! isBitSet(x, i))
                return i;
        }
        return -1;
    }

    public static int findLeftMostUnsetBit(int x) {
        int k = findLeftMostSetBit(x);
        for (int i = k; i >= 0; i--) {
            if (! isBitSet(x, i))
                return i;
        }
        return -1;
    }

    public static1+ void main(String[] args) {
        int x = 
            (1 << 0) |
            (1 << 1) |
            (1 << 4) |
            (1 << 5) |
            (1 << 6) |
            (1 << 8);
        System.out.println(findLeftMostUnsetBit(x));
        System.out.println(findRightMostUnsetBit(x));
    }

}

Если я не ошибаюсь, моя текущая реализация занимает линейное время.Можем ли мы сделать лучше?

Ответы [ 2 ]

5 голосов
/ 27 июня 2011

Ниже приведен исходный код Integer.numberOfLeadingZeros.Как уже указывалось, это взято из HD (Восторг Хакера Генри С. Уорреном, младшим)

Основная идея заключается в использовании бинарного поиска вместо итерации битов, один за другим.Пожалуйста, проверьте книгу, если вы интересуетесь мелочами.Это замечательное произведение искусства. 

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;
}
4 голосов
/ 27 июня 2011

В классе Integer доступны методы.

Integer.numberOfTrailingZeros(Integer.lowestOneBit(~yourValue)) будет делать это для младшего неустановленного бита, для старшего это немного сложнее, так как сначала мы должны определить самый старший установленный бит. 

int leadingZeroBits = Integer.numberOfLeadingZeros(Integer.highestOneBit(yourValue));
result = Integer.
       numberOfTrailingZeros(Integer.highestOneBit((~yourValue)<<leadingZeroBits)
      -leadingZeroBits;`

Должно сделать это для старшего неустановленного бита.

И это может быть быстрее, чем линейное время, поскольку у процессоров часто есть машинные инструкции для быстрого определения начального / конечного нулевого бита (но не уверен, что vm использует их. РЕДАКТИРОВАТЬ: теперь я уверен; -).

РЕДАКТИРОВАТЬ : Похоже, они добавили использование asm intrinsics для начальных / конечных нулей в 1.6.0_18, ID 6823354

...