找到一个非常大的数字的最右边的未设置位

Question

如何在 C++ 中获取数字 N 最右边未设置的位位置。

1<=N<=2^60

存储为数字不起作用，因为 2^60 只能存储在字符串中。因此以下不起作用

long long getBitUtil(long long n) { 
    return log2(n&-n)+1; 
} 

long long getBit(long long n) { 
    return getBitUtil(~n);         
}

Answer 1

试试这个。代码是自我解释的注释

int getRightmostUnSetBit(string s, int pos)
{
    int l= s.size();
    int lc = s[l-1];
    if(lc>=48 && lc<=57 && lc%2 ==0)
        return pos; // if last digit is even return position
    else
    {// divide the number into half and call function again.
        string s2 = "";
        int rem =0;
        for(int i =0; i<l;i++)
        {
            int d = s[i]-'0';
            d = rem *10 + d;
            int q = d/2;
            rem = d%2;
            s2.push_back('0'+q);
        }
        return getRightmostUnSetBit(s2,pos+1); //call for s2
    }
}

接受字符串输入并从 main 调用

int pos = getRightmostUnSetBit(s,1);// will not work if s is "0" or similar to "000...". So check for it before function calling.

Answer 2

对于正规整数，书上基本给出了解法Hackers Delight。我只能参考书。我无法复制。但是第 2.1 节已经给出了很好的提示。

根据您的 OS，您很可能拥有 64 位数据类型。对于 64 位数据类型，您仍然可以对给定的数字范围使用算术解决方案。除此之外，您应该使用字符串表示形式。

然后我们会将以字符串形式给出的大十进制数转换为包含其二进制等价物的字符串。

然后我们在生成的二进制字符串中搜索最后一个 0。

秘诀是将以字符串形式给出的数字除以 2。这可以按照我们在学校在一张纸上学到的那样来完成。

然后检查数字是偶数还是奇数，并在结果字符串中分别放入 1 或 0。

这适用于任意大的数字。限制因素（但这里不是真的）是生成的二进制字符串的长度。那必须适合 std::string :-)

参见：

#include <string>
#include <iostream>
#include <bitset>
#include <iterator>
#include <regex>
#include <stack>
#include <algorithm>

// Odd numbers. We will find out, if a digit is odd or even
std::string oddNumbers{ "13579" };

// Devide a number in a string by 2. Just like in school on a piece of paper
void divideDecimalNumberAsStringBy2(std::string& str)
{
    // Handling of overflow during devisions
    unsigned int nextNumberToAdd{ 0 };
    // The resulting new string
    std::string newString{};
    // Go through all digits, starting from the beginning
    for (char& c : str) {
        // Get overflow for next round
        unsigned int numberToAdd = nextNumberToAdd;
        // Get the overflow value for the next devision run. If number is odd, it will be 5
        nextNumberToAdd = (oddNumbers.find(c) != std::string::npos) ? 5 : 0;
        // Do the devision. Add overflow from last round
        unsigned int newDigit = (c - '0') / 2 + numberToAdd;
        // Build up newe string
        newString += static_cast<char>(newDigit + '0');
    }
    // Remove leading zeroes
    str = std::regex_replace(newString, std::regex("^0+"), "");
}

// Convert a string with a big decimal number to a string with a binar representation of the number
std::string convertDecimalStringToBinaryString(std::string& str)
{
    // Resulting string
    std::string binaryDigits{};
    // Until the string is empty. Will be shorter and short because of devision by 2
    while (!str.empty()) {
        // For an even number we add 0, for an odd number we add 1
        binaryDigits += (oddNumbers.find(str.back()) == std::string::npos) ? '0' : '1';
        // And devide by 2
        divideDecimalNumberAsStringBy2(str);
    }
    // Bits come in wrong order, so we need to revers it
    std::reverse(binaryDigits.begin(), binaryDigits.end());
    return binaryDigits;
}

int main()
{
    // Initial string with a big number. Get input from user
    std::string bigNumber{};
    std::cout << "Enter big number: ";
    std::cin >> bigNumber;

    // Convert it
    std::string binaryDigits = convertDecimalStringToBinaryString(bigNumber);
    
    // Find the last 0
    unsigned int posOfLast0 = binaryDigits.rfind('0');

    // Show result
    if (posOfLast0 == std::string::npos) 
        std::cout  << "\nNo digit is 0 --> " << binaryDigits << '\n';
    else
        std::cout << "\nSize of resulting string: "<< binaryDigits.size() <<  "\nPos of last 0: " << posOfLast0+1  << "\nBinary String:\n\n" << binaryDigits << '\n';

    return 0;
}

找到一个非常大的数字的最右边的未设置位

Find Rightmost unset bit of a very large number

c++

bit