Does Julia has bitwise circular shift?

General Usage
1

This documentation page lists the logical and arithmetic shift, as well as the bitwise NOT, AND, OR and XOR. However, the circular shift is absent.

Does Julia has a bitwise circular shift? If yes, where can I find it’s documentation? If not, is it possible to implement it with performance similar to the other bitwise operations?

2

I don’t think it exists, but for Int64 this should work and be about 3x slower than other bitshifts (since it uses 3 of them). You could easily enough write methods for other types of Integer, but I don’t know of a way in Julia to automatically get the number of bits in an integer.

function circshift(x, n)
    return (x<<n) | (x>>(muladd(8, sizeof(x), -n)
end

EDIT: now should work for any Integer subtype

1 Like
3

sizeof(x) or sizeof(typeof(x)) gives the amount of bytes

1 Like
4

Hot off the press: bitrotate

https://docs.julialang.org/en/v1.5/base/math/#Base.bitrotate

help?> bitrotate
search: bitrotate

  bitrotate(x::Base.BitInteger, k::Integer)

  bitrotate(x, k) implements bitwise rotation. It returns the value of x with its bits rotated left k times. A negative value of k will rotate to the right instead.

  │ Julia 1.5
  │
  │  This function requires Julia 1.5 or later.

  julia> bitrotate(UInt8(114), 2)
  0xc9

  julia> bitstring(bitrotate(0b01110010, 2))
  "11001001"

  julia> bitstring(bitrotate(0b01110010, -2))
  "10011100"

  julia> bitstring(bitrotate(0b01110010, 8))
  "01110010"
11 Likes
5 
(x << ((sizeof(T) << 3 - 1) & k)) | (x >>> ((sizeof(T) << 3 - 1) & -k))

is the body of the method. The biggest difference is that this actually can rotate in both directions as opposed to mine which was unidirectional.

1 Like
6

It came right when I need :grinning:, it’s timing couldn’t be better!

7

Actually, it appears to be just as fast as an ordinary bitshift. It seems that the compiler is smart enough to optimize it into a single bitrotate operation (from Circular shift - Wikipedia):

Unfortunately, many programming languages, including C, do not have operators or standard functions for circular shifting, even though virtually all processors have bitwise operation instructions for it […] some constructs in standard ANSI C code may be optimized by a compiler to the “rotate” assembly language instruction

3 Likes