Add ror and rol functions for rotating bits

[anaveragehuman]

Closes: #11592

[ararslan]

Welcome, and thanks for the contribution! This is a very nice and tidy first PR, great work. The only thing it needs is a compat annotation in the docstrings of the added functions, e.g.

!!! compat "Julia 1.4"
    This function requires Julia 1.4 or later.

[GregPlowman]

Could at least one of the examples show wrap-around?

[stevengj]

Do we really need two functions for this, since ror(x, -k) == rol(x, k) and looks like it should produce equivalent efficiency?

Should we call it ror or just add a new method to circshift for an integer first argument as suggested here by @StefanKarpinski?

[mbauman]

This is great, thank you! It looks like constant folding can handle the mask computation:

julia> ror(x::T, k::Integer) where {T <: Integer} = (x >>> ((sizeof(T) << 3 - 1) & k)) | (x <<  ((sizeof(T) << 3 - 1) & -k))
ror (generic function with 11 methods)

julia> @code_native debuginfo=:none ror(2,1)
	.section	__TEXT,__text,regular,pure_instructions
	movl	%esi, %ecx
	rorq	%cl, %rdi
	movq	%rdi, %rax
	retq
	nopl	(%rax)

This would, of course, just rely upon duck-typing (the lack of a sizeof "quack") to throw the error for BigInt, where this operation isn't well-defined. I think that's fine, though. Are there any other downsides to this general definition?

[mbauman]

Should we call it ror or just add a new method to circshift for an integer first argument as suggested here by @StefanKarpinski?

I don't think it fits the generic definition of circshift!. We don't think of bits of an integer as "data in [a collection];" we don't use pop! to remove the first bit and shift all bits down; we don't use indexed assignment to change bits in an integer. I think it deserves its own name. Whether it needs two names, however, is worth considering.

[ararslan]

That's a very good point. circshift +1 retracted.

[mbauman]

One thing that I think would be helpful would be a first-class TinyFixedSizeBitArray that just wraps a single integer and exposes its bits as elements in a fixed-size array. There have been requests for it more generally on discourse (and elsewhere) IIRC — and I'd bet that we could make circshift on such a wrapper distill down to just a rorq. :)

[vtjnash]

I know that llvm and assembly gives these rather cryptic names (fshl and fshr, https://llvm.org/docs/LangRef.html#llvm-fshl-intrinsic), but I feel like these may be just far enough outside the standard lexicon that they should use names instead of abbreviations. Maybe rotateright and rotateleft?

We don't think of bits of an integer as "data in [a collection];" we don't use pop! to remove the first bit and shift all bits down

True, but the complementary set of shift operators (<<, >>, >>>) are generic between BitArrays and Integers.

[stevengj]

I still don't understand why we need two functions here when a negative shift works fine. If we don't like circshift, maybe it could be called bitrotate?

[StefanKarpinski]

bitrotate would be fine. I think the main thing is just that ror and rol are traditional names. But the fact that the name of the test set is "bit rotate" is suggestive that bitrotate would be good.

[StefanKarpinski]

Ok, nice. I guess now the question is which way should be the default rotation direction? Is it just me or does left rotation, i.e. towards more significant bits, seem like the natural positive direction?

[StefanKarpinski]

Here are some cases of functions named bitrotate:

• https://docs.oracle.com/cd/E57340_01/DR/Bitrotate.html
• https://www.autoitscript.com/autoit3/docs/functions/BitRotate.htm
• https://www.mathworks.com/matlabcentral/fileexchange/30679-bitrotate?focused=5179419&tab=function

They all consider positive shifts to rotate left and negative shifts to rotate right. It seems like the primary reason for having left and right rotate functions is this potential ambiguity.

[anaveragehuman]

Is it just me or does left rotation, i.e. towards more significant bits, seem like the natural positive direction?

I tried to keep it consistent with circshift, which rotates to the right. Do we know which is more commonly used?

[stevengj]

I tried to keep it consistent with circshift, which rotates to the right.

"Left" and "right" are ambiguous labels.

circshift with a positive shift rotates towards increasing indices. The conventional "index" of a bit is in order of significance, so the analogous bitrotate would rotate left.

[StefanKarpinski]

That's also what all the versions I linked to do. It also makes more sense to me that positive bit rotation should increase the power of each bit while negative bit rotation should decrease it.

[StefanKarpinski]

I had missed that you updated this to shift bits in the right (left) direction. This looks good to me.

[StefanKarpinski]

You seem to have force pushed over my merge of this, in which I tweaked the NEWS entry for bitrotate to match bitreverse more closely.

[StefanKarpinski]

Thanks for the contribution!