`
standalone
  • 浏览: 595228 次
  • 性别: Icon_minigender_1
  • 来自: 上海
社区版块
存档分类
最新评论

Find the previous and next nearest number with same 1 bits

阅读更多
Problem:
Given an integer, print the next smallest and next largest number that have the same number of 1 bits in their binary representation

Solution from CareerCup book:

public static boolean GetBit(int n, int index) {
    return ((n & (1 << index)) > 0);
}

public static int SetBit(int n, int index, boolean b) {
    if (b) {
        return n | (1 << index);
    } else {
        int mask = ~(1 << index);
        return n & mask;
    }
}

public static int GetNext_NP(int n) {
    if (n <= 0) return -1;

    int index = 0;
    int countOnes = 0;

    // Find first one.
    while (!GetBit(n, index)) index++;

    // Turn on next zero.
    while (GetBit(n, index)) {
        index++;
        countOnes++;
    }
    n = SetBit(n, index, true);

    // Turn off previous one
    index--;
    n = SetBit(n, index, false);
    countOnes--;

    // Set zeros
    for (int i = index - 1; i >= countOnes; i--) {
        n = SetBit(n, i, false);
    }

    // Set ones
    for (int i = countOnes - 1; i >= 0; i--) {
        n = SetBit(n, i, true);
    }

    return n;
    
}

public static int GetPrevious_NP(int n) {
    if (n <= 0) return -1; // Error

    int index = 0;
    int countZeros = 0;

    // Find first zero.
    while (GetBit(n, index)) index++;

    // Turn off next 1.
    while (!GetBit(n, index)) {
        index++;
        countZeros++;
    }
    n = SetBit(n, index, false);

    // Turn on previous zero
    index--;
    n = SetBit(n, index, true);
    countZeros--;

    // Set ones
    for (int i = index - 1; i >= countZeros; i--) {
        n = SetBit(n, i, true);
    }

    // Set zeros
    for (int i = countZeros - 1; i >= 0; i--) {
        n = SetBit(n, i, false);
    }

    return n;
}

分享到:
评论

相关推荐

Global site tag (gtag.js) - Google Analytics