`
standalone
  • 浏览: 611325 次
  • 性别: 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;
}

分享到:
评论

相关推荐

    kgb档案压缩console版+源码

    where y_i is the i'th bit, and the context is the previous i - 1 bits of uncompressed data. 2. PAQ6 MODEL The PAQ6 model consists of a weighted mix of independent submodels which make predictions ...

    k-nearest-neighbors-from-global-to-local

    However, a critical aspect of successfully applying the weighted K-NN algorithm lies in choosing the optimal number of nearest neighbors \( k \), the weight vector \( \alpha \), and the distance ...

    k-Nearest Neighbor Classification

    pattern on the basis of its nearest neighbors in a recorded data set is addressed from the point of view of Dempster-Shafer theory. Each neighbor of a sample to be classified is considered as an item ...

    lle.rar_ISOMAP_LLE sparse_The Best at It_find fixed points_lle

    Finally, it uses an eigenvector-based optimization technique to find the low-dimensional embedding of points, such that each point is still described with the same linear combination of its neighbors...

    Traveling-Salesman-Problem---Nearest-Neighbor.rar_Arranged_route

    The nearest neighbour (NN) algorithm (a greedy algorithm) lets the salesperson choose the nearest unvisited city as his next move. This algorithm quickly yields an effectively short route. For N ...

    Computational Statistics Handbook with MATLAB, 3rd Edition

    Computational Statistics Handbook with MATLAB®, Third Edition covers today’s most commonly used techniques in computational statistics while maintaining the same philosophy and writing style of the ...

    图像处理DCT compression, dithering, image interpolation

    (b) Use the same process in (a) with image transformed to YIQ color model and show the reconstructed image in RGB space. [3 images] Compute the PSNR values of the three reconstructed images and ...

    nearest neighbor query and reverse nearest neighbor query

    两种重要的查询类型是最近邻(Nearest Neighbor, NN)查询和反向最近邻(Reverse Nearest Neighbor, RNN)查询。NN查询旨在找到距离给定查询点最近的数据点,而RNN查询则是找出所有将给定查询点视为其最近邻的数据点...

    The Inverted Multi-Index.pptx

    improve the speed of approximate nearest neighbor search on the dataset of 1 billion SIFT vectors compared to the best previously published systems, while achieving better recall and incurring only ...

    DIBSection Class VB

    &lt;br&gt;Dim tSA As SAFEARRAY2D Dim bDib() As Byte &lt;br&gt; ' Get the bits in the from DIB section: With tSA .cbElements = 1 .cDims = 2 .Bounds(0).lLbound = 0 ' Height of ...

    Using DIB Sections in VB

    &lt;br&gt;Dim tSA As SAFEARRAY2D Dim bDib() As Byte &lt;br&gt; ' Get the bits in the from DIB section: With tSA .cbElements = 1 .cDims = 2 .Bounds(0).lLbound = 0 ' Height of ...

    Mastering Machine Learning with scikit-learn [2017,第二版]

    Predict the values of continuous variables using linear regression and K Nearest Neighbors Classify documents and images using logistic regression and support vector machines Create ensembles of ...

    FAST APPROXIMATE NEAREST NEIGHBORS WITH AUTOMATIC ALGORITHM CONFIGURATION

    ### 关键知识点解析 #### 一、概览与背景 - **高维空间中的最近邻搜索**:在计算机视觉领域,最耗时的部分通常涉及在高维空间中进行最近邻匹配。 - **精确算法的局限性**:对于解决高维问题,目前尚未找到比线性...

    Mastering Machine Learning with scikit-learn -2017.7.24

    Predict the values of continuous variables using linear regression and K Nearest Neighbors Classify documents and images using logistic regression and support vector machines Create ensembles of ...

    K-DBSCAN: Identifying Spatial Clusters With Differing Density Levels

    OPTICS and Shared Nearest Neighbour (SNN) algorithms have the capabilities of clustering variable density datasets but they have their own limitations. Both fail to detect overlapping clusters. Also,...

    雷达技术知识

    and the Graduate School of the University of Oregon in partial fulfillment of the requirements for the degree of Master of Science March 2009 11 "Effectiveness of Extracting Water Surface Slopes from ...

    Data Science from Scratch First Principles with Python

    If you have an aptitude for mathematics and some programming skills, author Joel Grus will help you get comfortable with the math and statistics at the core of data science, and with hacking skills ...

    Hands_On_Machine_Learning_with_Scikit_Learn_and_TensorFlow book and code

    • The main challenges of Machine Learning, in particular underfitting and overfitting (the bias/variance tradeoff). • Reducing the dimensionality of the training data to fight the curse of ...

Global site tag (gtag.js) - Google Analytics