我在我编写的一些c代码中遇到了一个错误,虽然它相对容易修复,但我希望能够更好地理解它背后的问题.基本上发生的事情是我有两个无符号整数(实际上是uint32_t),当应用模数运算时,产生了一个负数的无符号等价物,一个已被包裹的数字,因此是"大".这是一个示例程序来演示:
#include <stdio.h>
#include <stdint.h>
int main(int argc, char* argv[]) {
uint32_t foo = -1;
uint32_t u = 2048;
uint64_t ul = 2048;
fprintf(stderr, "%d\n", foo);
fprintf(stderr, "%u\n", foo);
fprintf(stderr, "%lu\n", ((foo * 2600000000) % u));
fprintf(stderr, "%ld\n", ((foo * 2600000000) % u));
fprintf(stderr, "%lu\n", ((foo * 2600000000) % ul));
fprintf(stderr, "%lu\n", foo % ul);
return 0;
}
这会在我的x86_64机器上产生以下输出:
-1
4294967295
18446744073709551104
-512
1536
2047
1536是我期待的数字,但是(uint32_t)( - 512)是我得到的数字,正如你可能想象的那样,它会让人感觉不舒服.
所以,我想我的问题是:为什么两个无符号数之间的模数运算,在这种情况下,产生的数字大于除数(即负数)？这种行为是首选的原因吗？
假设我有一个包含数字的整数数组,我想取存储在其中的模数,即
int a[36]={1,2,3,4,5,6,7,8,9,1,2,3,4,5,6,7,8,9,1,2,3,4,5,6,7,8,9,1,2,3,4,5,6,7,8,9}
并将其转换为数字987654321987654321987654321987654321.
在C语言long long int允许只有10 ^ 18.我想用10 ^ 9 + 7取模数.我怎样才能做到这一点？
程序:
int main()
{
int a[36]={1,2,3,4,5,6,7,8,9,1,2,3,4,5,6,7,8,9,1,2,3,4,5,6,7,8,9,1,2,3,4,5,6,7,8,9};
long long int temp=0;
int i;
for(i=0;i<36;i++)
{
temp=temp+a[i]*pow(10,i);
}
temp=temp%1000000007;
printf("%lld",temp);
return 0;
}
背景
当我偶然发现gcc trunk中的一个新优化(将是版本9.x)时,我正在使用c中的素数进行操作,该优化将模数比较优化为0整数乘法并使用幻数进行比较.换句话说x%prime==0就变成了x*Magic_mul<=Magic_cmp
_Bool mod(unsigned x){return x % Constant == 0;}
mod:
imul edi, edi, Magic_mul
cmp edi, Magic_cmp
setbe al
细节
基于看到asm输出,它对所有整数进行了这些优化(好吧,至少是素数)我将它们转换为十六进制以帮助查看模式,但目前还不是很明显.
//32bit examples for _Bool mod_n(unsigned x){return x%n==0;};
//note: parameter is unsigned but it becomes a signed multiply
x%3==0; // x*0xAAAAAAAB <= 0x55555555
x%5==0; // x*0xCCCCCCCD <= 0x33333333
x%7==0; // x*0xB6DB6DB7 <= 0x24924924
x%11==0; // x*0xBA2E8BA3 <= 0x1745D174
x%13==0; // x*0xC4EC4EC5 <= 0x13B13B13
x%17==0; // x*0xF0F0F0F1 <= 0x0F0F0F0F
x%19==0; // x*0x286BCA1B <= 0x0D79435E
x%23==0; // …我只是听说过x mod (2^32-1),并x / (2^32-1)会很容易,但如何？
计算公式:
x n =(x n-1 + x n-1/b)mod b.
因为b = 2^32,它很容易x%(2^32) == x & (2^32-1); 和x / (2^32) == x >> 32.(这里的^不是XOR).当b = 2 ^ 32 - 1时如何做到这一点.
在页面https://en.wikipedia.org/wiki/Multiply-with-carry.他们说" arithmetic for modulus 2^32 ? 1 requires only a simple adjustment from that for 2^32".那么"简单调整"是什么？
以下列方式很容易在0和1之间"切换":
int i = 0;
i = (++i) % 2; // i = 1
i = (++i) % 2; // i = 0
同样,我发现可以在3到5之间"切换":
int i = 3;
i = (((i * 2) - 1) % 3) + 3; // i = 5
i = (((i * 2) - 1) % 3) + 3; // i = 3
虽然这感觉很麻烦,但我正在寻找一种更简洁的方法来做到这一点.可以简化吗？如果是这样,怎么样？顺便说一下,我实际上是在用这个东西.
假设我有Long someLong = 1004L.我可以使用什么有效的方法将其舍入到1000L？请注意,我实际上并不知道,someLong == 1004L所以我不能简单地这样做someLong -= 4L;.我需要一个可推广的方法.我也希望能够向下舍入到每个5而不是每个10,例如一个1005L舍入到的函数(因为如果我们舍入为5s然后它将向上舍入而不是向下舍入).
更多的例子..可能是我有1926L,我想要圆润到5我需要的意思1925L.或者我需要四舍五入到10我需要的意义1930L.
所以在我的教科书中有一个使用f#的递归函数的例子
let rec gcd = function
| (0,n) -> n
| (m,n) -> gcd(n % m,m);;
使用此功能,我的教科书通过执行以下内容给出了示例
gcd(36,116);;
并且由于m = 36而不是0,那么它的第二个句子是这样的:
gcd(116 % 36,36)
gcd(8,36)
gcd(36 % 8,8)
gcd(4,8)
gcd(8 % 4,4)
gcd(0,4)
and now hits the first clause stating this entire thing is = 4.
我没有得到的是这个(%)百分号/操作符或此连接中调用的任何内容.对于一个实例我不知道如何
116 % 36 = 8
我现在已经多次转过头了,我无法想象这怎么会变成8？
我知道对于那些知道这一点的人来说这可能是一个愚蠢的问题,但我非常感谢你的帮助.
#include <bits/stdc++.h>
#define mx 1000005
#define mod 1000003
using namespace std;
long long arr[mx];
int fact()
{
arr[0]=1;
for(int i=1; i<mx; i++)
{
arr[i]=((i%mod)*(arr[i-1]%mod))%mod;
}
}
int main()
{
int t;
long long a,b,C,E;
fact();
cin>>t;
while(t--)
{
cin>>a>>b;
C=(arr[a]%mod)%mod;
E=((arr[b])%mod)*((arr[a-b])%mod)%mod;
}
}
在这个问题中我必须计算 (C/E)%1000003。我如何使用模乘逆技术来做到这一点？还有其他方法可以计算这个吗？
我有一个关于使用按钮切换一些图像的教程，这是代码
public class MainActivity extends AppCompatActivity {
private static ImageView andro;
private static Button buttonswitch;
int current_image_index = 0;
int[] images = {R.mipmap.andro_img,R.mipmap.apple_image,R.mipmap.ic_launcher,R.mipmap.ic_launcher_round};
@Override
protected void onCreate(Bundle savedInstanceState) {
super.onCreate(savedInstanceState);
setContentView(R.layout.activity_main);
buttonClick();
}
public void buttonClick() {
andro = (ImageView) findViewById(R.id.imageView);
buttonswitch = (Button) findViewById(R.id.button);
buttonswitch.setOnClickListener(
new View.OnClickListener() {
@Override
public void onClick(View view) {
current_image_index++;
current_image_index = current_image_index % images.length;
andro.setImageResource(images[current_image_index]);
}
}
);
}
}
这部分我真的很困惑：
@Override
public void onClick(View view) {
current_image_index++;
current_image_index = current_image_index % images.length; …如何%使用 Python计算 C %？两者之间的区别在于它们处理否定论点的方式。
在这两种语言中， 的%定义方式使这种关系（//整数除法）成立：
a // b * b + a % b == a
但是a // bC 和 Python 中的舍入不同，导致a % b.
例如，在 C 中（其中整数除法仅/使用int操作数）我们有：
int a = 31;
int b = -3;
a / b; // -10
a % b; // 1
在 Python 中：
a = 31
b = -3
a // b # -11
a % b # -2 …