Ruby Ruby 固定 bit 数循环左移解决方法讨论

Kirisames · 2021年01月21日 · 最后由 aaline57963 回复于 2021年02月18日 · 385 次阅读

需求

希望经过讨论后能得到一个高效的循环左移方法

环境

kali 2020.04
ruby 3.0.0

思考

均以 8bit 为例子

1. 数组法

运用数组模拟循环。

def circle_left_array(x, rotate)
  len = x.bit_length
  a = []
  (len - 1).downto(0) { |i| a.push(x[i]) }
  a.rotate!(rotate)
  return Integer(a.join,2).to_s(10).to_i
end

2. 字符串法

运用字符串的截位和拼接(在 String 中新增方法)

def cleft_shift(n) #self为2进制串,n为左移次数

  n = n % self.length

  temp = self[0,n]

  return self[n,self.length]+temp
end

这是我目前能够想到的两种方法,如果有更高效的方法希望能够一起交流。

<< 不香?

pynix 回复

bit 数固定的话就不香了。

(n << 1 & 255) + (n >> 7) # 8 位
(n << 1 & (2**m - 1)) + (n >> (m - 1)) # m 位
ug0 回复

哦哦,感谢

Kirisames 回复

要香就直接写 C 扩张,C 位移操作高效。

extconf.rb

require 'mkmf'
$CFLAGS << ' -O3 '
$CFLAGS << ' -std=c99'
create_makefile('rotate')

rotate.h

#ifndef ROTATE_H
#define ROTATE_H
/* Nothing to expose */
#endif

rotate.c

#include "rotate.h"
#include <ruby.h>
#include <stdint.h>
#ifdef __x86_64__
#ifdef __linux__
#include <x86intrin.h>
#endif
#endif
/* Support more arch/cc if you want */

static VALUE rb_mRotate;
static VALUE rb_mRotate_Native;
static VALUE rb_mRotate_Native_U64;

static VALUE rotate_native_u64_rb_left(VALUE self, VALUE src, VALUE bits);

void Init_rotate(void)
{
    rb_mRotate = rb_define_module("Rotate");
    rb_mRotate_Native = rb_define_module_under(rb_mRotate, "Native");
    rb_mRotate_Native_U64 = rb_define_module_under(rb_mRotate_Native, "U64");
    rb_define_module_function(rb_mRotate_Native_U64, "left", rotate_native_u64_rb_left, 2);
}

static VALUE rotate_native_u64_rb_left(VALUE self, VALUE src, VALUE rot)
{
    uint64_t source = NUM2ULL(src);
    uint64_t rotate = NUM2ULL(rot);

    return ULL2NUM(__rolq(source, rotate));
}

Run ruby extconf.rb && make

test.rb

require_relative 'rotate'

puts Rotate::Native::U64.left(1,63)
# => 9223372036854775808
puts Rotate::Native::U64.left(1,64)
# => 1

需要 登录 后方可回复, 如果你还没有账号请 注册新账号