logo标签列表

C++位数组除法的余数

c++arraysbit
3

我有两个长度分别为200和10的二进制数组。我想用第二个数组去除第一个数组并得到余数。在C++中，如何使用位运算而不是将它们转换为十进制并使用模运算来实现？

一个例子会更好。你所说的“位数组”是由值为1和0的200个整数表示，还是指200个位被“打包”成32位整数？ - Mike Dinescu
1
长除法。在二进制中比十进制更容易进行，因为对于每个数字，只有两种选择：它被整除（1）或者不被整除（0）。 - Mark Ransom
我基本上将一个长度为200的字符串转换为位数组。一些字符是'1'，而其他字符是'0'。 - SBDK8219
@MarkRansom，你能否再详细解释一下长除法？ - SBDK8219
你只需要余数，还是需要商数？ - Christopher Oicles
@ChristopherOicles 只剩下其余部分 - SBDK8219
3个回答
2
这里是使用std::bitset实现的代码。
找到余数的方法是将除数向左移，直到它大于或等于被除数，然后开始将其向右移回到原始位置。对于每个新的移位除数的值，如果它大于当前余数（起始为被除数），则减去它以得到一个新的余数。如果除数等于余数，则返回0。一旦除数达到其原始未移位位置，并从余数中减去（如果需要），则余数就完成了。
函数BsMod接受被除数和除数参数，并将被除数参数替换为余数，因此请确保该参数是左值以便获取结果。
默认测试（在main函数中）随机创建二进制字符串并打印出二进制结果。这种验证方式比较困难，因此我创建了另一个随机测试（Test()函数），它使用整数值来自动验证结果。
#include <iostream>
#include <bitset>
#include <string>
#include <ctime>
#include <cstdlib>

// subtracts b from a, replacing a with the result
template <typename A, typename B>
void Subtract(A &a, const B &b) {
    static const std::size_t minc = a.size() < b.size() ? a.size() : b.size();
    bool borrow = false;
    for(std::size_t i = 0; i<minc; ++i) {
        const bool dif = a[i] ^ b[i] ^ borrow;
        borrow = (a[i] && b[i] && borrow) || (!a[i] && (b[i] || borrow));
        a[i] = dif;
    }
    for(std::size_t i=minc; borrow && i<a.size(); ++i) {
        a[i] = borrow = !a[i];
    }
}

// Returns the index of the highest set bit in b
// Returns unsigned -1 if all bits are 0
template <typename B>
std::size_t HiBit(const B& b) {
    for(std::size_t i = b.size()-1; i+1; --i) {
        if(b[i]) return i;
    }
    // b is zero
    return ~std::size_t(0);
}

// Compare returns 1 if a>b, 0 if a==b or -1 if a<b
template <typename B>
int Compare(const B &a, const B &b) {
    const std::size_t high = a.size()-1;
    for(std::size_t i=high; i+1; --i) {
        if(a[i] != b[i]) {
            return int(a[i]) - int(b[i]);
        }
    }
    return 0;
}

// nr is changed from the dividend to the remainder
template <typename B>
void BsMod(B &nr, B d) {
    const std::size_t hi_n = HiBit(nr);
    const std::size_t hi_d = HiBit(d);
    if(hi_d > hi_n) return;                            // nr < d, keep n as r
    if(hi_d == hi_n && Compare(nr, d) == -1) return;   // nr < d, keep n as r

    const std::size_t dshift = hi_n - hi_d;
    d <<= dshift;

    for(std::size_t i=0; i<=dshift; ++i) {
        const int cmp = Compare(nr, d);
        if(cmp == 0) { nr = B(); return; } // d evenly divides nr, so r is 0
        if(cmp > 0) {  // nr > shifted d
            // the quotient would accumulate a 1 bit here, at the d shift position
            Subtract(nr, d);
        }
        d >>= 1;   // divide d by 2, shift back toward original position
    }
}

template <typename B>
unsigned long long bs_to_ull(const B& b) {
    unsigned long long result = 0;
    for(std::size_t i=0; i<sizeof(unsigned long long)*8; ++i) {
        result |= static_cast<unsigned long long>(b[i]) << i;
    }
    return result;
}

template <typename B>
void ull_to_bs(B& b, unsigned long long n) {
    b.reset();
    for(std::size_t i=0; i<sizeof(unsigned long long)*8; ++i) {
        if(n & ((unsigned long long)1 << i)) b.set(i, true);
    }
}

unsigned long long rand_ull() {
    unsigned long long r = 0;
    unsigned long long b = 0;
    for(int i=0; i<sizeof(unsigned long long); ++i) {
        r = r * 33 + rand();
        b ^= rand();
        b <<= 8;
    }
    return ((r << sizeof(unsigned long long)*4) | (r >> sizeof(unsigned long long )*4)) ^ b;
}

void Test(unsigned long long max=0, int max_iters=0) {
    typedef unsigned long long uit;
    typedef std::bitset<sizeof(unsigned long long)*8+8> bs;
    typedef unsigned long long uit;

    int iter_count = 0;
    for(;;) {
        uit a = rand_ull();
        uit b = rand_ull();
        if(max) {
            a %= max;
            b %= max;
        }
        if(rand() & 255) {
            while(b > a) b >>= rand() & 3;
        }
        if(!b) continue;

        bs bsa;
        ull_to_bs(bsa, a);
        bs bsb;
        ull_to_bs(bsb, b);

        BsMod(bsa, bsb);

        uit ibsm = bs_to_ull(bsa);
        uit m = a % b;

        std::cout << a << " % " << b << " = " << m << "    :    " << ibsm << '\n';

        if(ibsm != m) {
            std::cout << "Error\n";
            return;
        }

        ++iter_count;
        if(max_iters && iter_count > max_iters) break;
    }
}

std::string RandomBinaryString(unsigned bit_count) {
    std::string binstr;
    for(unsigned i=0; i<bit_count; ++i) {
        binstr +=  ((rand() >> (i%5)) ^ i) & 1 ?  '1' : '0';
    }
    return binstr;
}

void TrimLeadingZeros(std::string& s) {
    if(s.length() < 2 || s[0] != '0') return;
    for(std::string::size_type i=1; i<s.length()-1; ++i) {
        if(s[i] != '0') {
            s = s.substr(i);
            return;
        }
    }
    s = s.substr(s.length()-1);
}

int main() {
    srand((unsigned int)time(0));
    //Test(0, 10);  // test with integer values (which are easy to auto-validate)
    //return 0;

    std::string a = RandomBinaryString(200);
    std::string b = RandomBinaryString(10);

    static const int max_bitount = 220;
    typedef std::bitset<max_bitount> bs;

    bs bsa(a);
    bs bsb(b);

    // both arguments must have the same type (number of bits)
    // bsa gets replaced with bsa modulo bsb
    BsMod(bsa, bsb); 


    std::string c = bsa.to_string();
    TrimLeadingZeros(c);

    std::cout << a << "\n   mod\n" << b << "\n   ==\n" << c << '\n';
}
谢谢！我明白你的逻辑了。当我使用你的代码时，我遇到了编译错误。那是因为模板的缘故。我对此不太熟悉。 - SBDK8219
@SBDK8219 你用什么编译器？ - Christopher Oicles
gcc 版本是 gcc (GCC) 4.4.7 20120313。我也尝试过像这样使用 C++11 $ g++ -std=c++0x your_file.cpp -o your_program。 - SBDK8219
嗯，它一定在抱怨<random>库和auto变量。我很快会有一个更兼容的新版本。 - Christopher Oicles
我正在使用IdeOne C++14编译器以及Visual C++ 2013进行测试。我即将进行一次编辑，这应该可以解决你的问题。稍等片刻... - Christopher Oicles
好的，我已经做了修改！ - Christopher Oicles
1
我首先会看一下使用std::bitset。这似乎比使用数组更容易。其次，阅读有关使用位运算执行模数的文章。我找到了其中一篇文章this。祝你好运。
谢谢！我一直在找这样的东西。我一定会试试的。 - SBDK8219
很高兴能够帮助，如果这个答案解决了您的问题，请点击答案旁边的勾选标记将其标记为已接受。更多信息请参见此处。 - Panda
0
首先，为您的两种类型的数字（200位和10位）定义移位减法。然后继续进行除法运算。
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接