位运算深度解析：左移、右移与memset应用

"位运算.pptx" 这篇内容主要讲述了计算机科学中的位运算，包括位运算的原理、应用以及一些相关的编程实践。位运算是计算机底层操作的基础，它涉及到数据在计算机内部的二进制表示。 首先，内容提到了正数和负数在计算机中的存储方式。对于正数，原码、反码和补码是相同的，都是其二进制表示。而对于负数，原码是其二进制表示，反码是除了符号位（最高位）之外的所有位取反，补码是在反码的基础上再加1。例如，-1的原码是[10000001]，反码是[11111110]，补码是[11111111]。 接着，介绍了`sizeof()`运算符，它用于获取变量或数据类型的字节数。例如，`short`类型占2字节，`int`占4字节，`long long`占8字节，`double`占8字节，`char`占1字节，字符串`s`的大小为8字节（指针大小），动态数组`int v[n]`的大小为4*n字节。 然后，讲解了`memset`函数，该函数用于将内存区域的每个字节设置为特定的值。`memset(s, NUM, n)`会将指针`s`指向的前n个字节设置为数值NUM。例如，将一个`int`类型的变量`a`用`memset(a, 1, 4)`填充后，`a`在16进制下表示为01010101，对应的十进制值为16843009。 位运算中，左移`<<`表示将数字的二进制位向左移动，高位补0；右移`>>`分为逻辑右移和算术右移，这里提到的是算术右移，它保留符号位，高位用符号位填充，低位舍弃。例如，`n<<1`相当于`n*2`，`n>>1`相当于`n/2`（整除）。 快速幂算法`ksm`被提及，这是一种在计算`a^b mod p`时提高效率的方法，其时间复杂度为O(log b)。给出的代码实现中，通过不断地将指数b进行拆分并利用幂的性质进行计算，大大减少了计算次数。 最后，内容提到了一个长整型乘法的问题，即`a * b mod p`。如果直接相乘可能会导致越界，因此可以采用类似快速幂的方法，将乘法转化为加法，即`a * b = (a * 2) * (b / 2) + a * (b % 2)`，但这种方法的时间复杂度会变为O(log b)。 总结起来，这篇内容涵盖了位运算的基本概念、C/C++中的`sizeof`运算符、`memset`函数的使用，以及快速幂算法在计算模幂和长整型乘法中的应用。这些知识对于理解计算机底层运作和编写高效的算法至关重要。