实现以下目标的最佳算法是什么:
0010 0000 => 0000 0100
转换从MSB-> LSB到LSB-> MSB.所有位必须反转; 也就是说,这不是字节顺序交换.
对于乘法大二进制矩阵(10Kx20K),我通常要做的是将矩阵转换为浮点数并执行浮点矩阵乘法,因为整数矩阵乘法非常慢(请看这里).
但这一次,我需要执行超过数十万次这样的乘法运算,甚至平均事情上的毫秒级性能提升.
我想要一个int或float矩阵作为结果,因为产品可能有非0或1的元素.输入矩阵元素都是0或1,因此它们可以存储为单个位.
在行向量和列向量之间的内积中(为了产生输出矩阵的一个元素),乘法简化为按位AND.添加仍然是添加,但我们可以添加具有填充计数功能的位,而不是单独循环它们.
一些其他布尔/二进制矩阵函数或位而不是计数它们,产生位矩阵结果,但这不是我需要的.
下面是一个示例代码,显示将问题形成为std::bitset, AND并且count操作比矩阵乘法更快.
#include <iostream>
using std::cout; using std::endl;
#include <vector>
using std::vector;
#include <chrono>
#include <Eigen/Dense>
using Eigen::Map; using Eigen::Matrix; using Eigen::MatrixXf;
#include <random>
using std::random_device; using std::mt19937; using std::uniform_int_distribution;
#include <bitset>
using std::bitset;
using std::floor;
const int NROW = 1000;
const int NCOL = 20000;
const float DENSITY = 0.4;
const float DENOMINATOR = 10.0 - (10*DENSITY);
void fill_random(vector<float>& vec) { …我试图在C中实现一个数据结构,这将允许我有效地操作**二进制**矩阵(仅包含1或0).我将解释我必须对此矩阵应用哪些操作,并想知道使用哪种最佳数据结构？
操作在字段F_2中完成(这意味着1 + 1 = 0,其他操作保持不变).我有一个k*n矩阵(k< n)调用H.最多k= 2325和n= 3009.
我必须对此矩阵执行的操作是:
我将仅使用行交换和行添加来部分对角化它.一旦完成,我将不再使用行操作,并将在此矩阵上运行大量(!)列添加(我的意思是"很多"是关于((nk)/ 2)³列添加)
我正在考虑矩阵的数据结构:
对于矩阵系数,我考虑在一个单个unsigned int中一次存储多个位的序列.例如,我可以将序列存储(11001011)到uint8_t 203(从二进制转换为十进制)
如果我这样做,我有两个选择:
我可以使用uint16_t或uint64_t系数在许多4*4或8*8子矩阵中分割我的矩阵H.
uint16_t或uint64_t？另外我想存储每一行中的多个uint32_t或uint64_t,然后操作我的部分对角化.接下来切换到将矩阵编码为n列向量以处理剩余操作的结构.
无论我使用什么方法,我都必须有效地访问nunsigned int(uint16,32或64)的第一位.我怎么做 ？