How to shift bits faster

General Usage
2

Thankfully, the compiler seems good at figuring that sort of thing out in practice. Eg, your & 63 example, or when the shift is constant:

julia> leftshift18(x) = x << 18
leftshift18 (generic function with 1 method)

julia> rightshift18(x) = x >> 18
rightshift18 (generic function with 1 method)

julia> @code_native leftshift18(1)
	.text
; ┌ @ REPL[1]:1 within `leftshift18'
; │┌ @ int.jl:450 within `<<' @ REPL[1]:1
	shlq	$18, %rdi
; │└
	movq	%rdi, %rax
	retq
	nopl	(%rax,%rax)
; └

julia> @code_native rightshift18(1)
	.text
; ┌ @ REPL[2]:1 within `rightshift18'
; │┌ @ int.jl:448 within `>>' @ REPL[2]:1
	sarq	$18, %rdi
; │└
	movq	%rdi, %rax
	retq
	nopl	(%rax,%rax)
; └

Or in common usages like random number generators:

julia> using RandomNumbers

julia> @code_native RandomNumbers.PCG.pcg_output(one(UInt), RandomNumbers.PCG.PCG_XSH_RS)
	.text
; ┌ @ bases.jl:85 within `pcg_output'
; │┌ @ int.jl:448 within `>>' @ bases.jl:74
	movq	%rdi, %rax
	shrq	$22, %rax
; │└
; │┌ @ int.jl:321 within `xor'
	xorq	%rdi, %rax
; │└
; │ @ bases.jl:84 within `pcg_output'
; │┌ @ int.jl:448 within `>>' @ int.jl:442
	shrq	$61, %rdi
; │└
; │ @ bases.jl:86 within `pcg_output'
; │┌ @ int.jl:800 within `+' @ int.jl:53
	addl	$22, %edi
; │└
; │┌ @ int.jl:442 within `>>'
	shrxq	%rdi, %rax, %rax
; │└
	retq
	nopw	(%rax,%rax)
; └

The above function has quite a few shifts:

@inline function pcg_output(state::T, ::Type{PCG_XSH_RS}) where T <: Union{pcg_uints[2:end]...}
    return_bits = sizeof(T) << 2
    bits = return_bits << 1
    spare_bits = bits - return_bits
    op_bits = spare_bits - 5 >= 64 ? 5 :
              spare_bits - 4 >= 32 ? 4 :
              spare_bits - 3 >= 16 ? 3 :
              spare_bits - 2 >= 4  ? 2 :
              spare_bits - 1 >= 1  ? 1 : 0
    mask = (1 << op_bits) - 1
    xshift = op_bits + (return_bits + mask) >> 1
    rshift = op_bits != 0 ? (state >> (bits - op_bits)) & mask : 0 % T
    state = state ⊻ (state >> xshift)
    (state >> (spare_bits - op_bits - mask + rshift)) % half_width(T)
end
3 Likes