Ruby Ruby 固定 bit 数循环左移解决方法讨论
需求
希望经过讨论后能得到一个高效的循环左移方法
环境
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
这是我目前能够想到的两种方法，如果有更高效的方法希望能够一起交流。
ug0
#3
2021年01月21日
(n << 1 & 255) + (n >> 7) # 8 位
(n << 1 & (2**m - 1)) + (n >> (m - 1)) # m 位
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
逃