知识卡片
循环左移保留被移出的位
循环左移把逻辑位流最左端移出的位绕到最右端,与补零而丢位的普通左移不同。本例重复做count轮单比特轮转:保存第一单元的高位,逐单元向左移,并把下一单元原高位接到前单元的低位,最后把保存位写到逻辑位置size−1。
因此跨单元传递方向是后单元高位→前单元低位,正文“前一字节最右给当前最左”不符合实际代码。逻辑末位可能不在最后单元的物理最低位,要按size−1定位;尾部未用位不当作被轮转数据。
本实现size>0才操作,逐轮扫描约⌈β/8⌉单元,成本O(count·β)模型;它未把count先对β取模,转很多圈会重复工作。调用方需合法位数、计数和缓冲空间,未执行旋转。
252/03015–03016先保存第一字节高位,后续字节高位写前一字节第7位,再左移当前字节,最终写bits逻辑size−1。注释/正文方向须跟代码区分;保存位与跨字节进位两者不可省略。
这张卡片看不懂?
这张卡片已通过人工审查,不再接受失败反馈。
已有反馈 · 0 条
还没有人提交反馈。
在整书笔记中的位置
- · 循环左移保留被移出的位
- · bit_xor
原书出处 · 2 处
- · 查看原书依据
bit_rot_left 返回值 无 描述 轮转缓冲区bits(含size位),将位值向左移count位。此操作完成后,处于最左端的count位移动到缓冲区最右端,而且其他的位也相应地轮转。 复杂度 O(nβ),其中β为每个缓冲区中位的个数,n为要轮转到左边的位数。
- · 查看原书依据
最左端位值,然后向左一位一位地移动每个字节的位值。在移动字节的过程中,将前一个字节最右边的位移到当前字节的最左边。当处理到最后一个字节时,将其最右边的位移动到首字节的最高位上。这个过程一直持续下去直到所有的位都轮转到位。 bit_rot_left的时间复杂度为O(nβ),其中n为要向左轮转的位的个数
参考来源
- 位置:《算法精解:C语言描述》第14章《位操作的接口定义》(spine1376;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1342.html;u248-ch14-009)。
- 结论依据:248轮转接口/03013原型与252全部说明、03015–03016完整j/i循环、bit_set上一单元末位和最终size−1代码实读,明确正文方向差异。
- 原始内容:bit_rot_left 返回值 无 描述 轮转缓冲区bits(含size位),将位值向左移count位。此操作完成后,处于最左端的count位移动到缓冲区最右端,而且其他的位也相应地轮转。 复杂度 O(nβ),其中β为每个缓冲区中位的个数,n为要轮转到左边的位数。
- 位置:《算法精解:C语言描述》第14章《bit_xor》(spine1379;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1345.html;u252-ch14-009)。
- 结论依据:252/03015–03016先保存第一字节高位,后续字节高位写前一字节第7位,再左移当前字节,最终写bits逻辑size−1。注释/正文方向须跟代码区分;保存位与跨字节进位两者不可省略。
- 原始内容:最左端位值,然后向左一位一位地移动每个字节的位值。在移动字节的过程中,将前一个字节最右边的位移到当前字节的最左边。当处理到最后一个字节时,将其最右边的位移动到首字节的最高位上。这个过程一直持续下去直到所有的位都轮转到位。 bit_rot_left的时间复杂度为O(nβ),其中n为要向左轮转的位的个数