Shift Rotate a binary number.

[Setat]

Hi,
I need to XOR two binary numbers bitwisely. (ex: 0010 xor 0111)
The second number should be right-shift-rotate by two bits first.
How I can shift-Rorate a for example 4-bit binary number? And then xor it with another 4-bit number bitwisely?
for example 0111 ====> into 1101?
then calculating 0010 xor 1101 bitwisely.

Would you plz help me about this?

[jonnin]

c++ lacks a rotate, it only has shifts, so you have to do it yourself.

bit xor is ^ by the way.

an example of rotating one spot:
tmp = (x & 1); //lets do 1001 for example. tmp is 1, the ones bit pulled off
x = x >> 1; //x is shifted: x is now 0100 << shifts the other way
x+= tmp*8; // x is 1100, adding 8 back. if tmp had been zero, does nothing.

but that only shifts one time, and doing it several times is inefficient.
the same idea will work for multiple spots, though. pull off the extreme end, as many bits as you shift, and put them on the other end, which is zeroed out after the shift.

this is one of those places where an inline assembly command is the right answer (for some values, not 4 bit). The CPU has a rotate instruction, or most/many of them do. Just call it. None of them work on 4 bit numbers though, they work on integers (1, 2, 4, 8 bytes).

an alternative is a lookup table. there are only 4 bits, so only 16 possible results from any rotation. Just code them up and get the answer directly. you can only shift 4 bits, then it repeats, so 4 tables or a 2d table of 16 covers multiple shifts. and, a number of values don't matter if you shift them anyway, eg 1111 or 0000.

[dutch]

Nevermind. Just a silly idea.

[mbozzi]

Someone may be able to simplify this:

See the specification of std::rotl
https://eel.is/c++draft/bit.rotate

I think the actual function declaration for std::rotl is lacking.
- It doesn't work on std::byte, which is silly; more importantly
- It invites errors (IMO) as a result of passing incorrectly-sized types.

Maybe it could be amended to read something like my_rotl

template <typename T> concept unsigned_integral 
  = requires { std::integral<T> && std::is_unsigned_v<T>; }; 

template <unsigned_integral T, unsigned_integral U> 
  constexpr T my_rotl(U n, int count = 1) 
    requires std::same_as<T, U>
  {
    return std::rotl(n, count);
  }

int main()
{
  static_assert(2 == my_rotl<unsigned>(1u));
}

After some thought I guess std::rotl is not as bad as it first appears because many accidental conversions would produce a signed type, which will not compile.

[seeplus]

If you can use as a minimum 8 bits as to opposed to 4, then you can use the c++20 std::rotr

#include <bit>
#include <bitset>
#include <iostream>

int main()
{
	const std::uint8_t i {0b0010};
	const std::uint8_t i1 {0b0111};
	const auto res {i ^ std::rotr(i1, 2)};

	std::cout << std::bitset<8>(i) << '\n';
	std::cout << std::bitset<8>(i1) << '\n';
	std::cout << std::bitset<8>(res) << '\n';
}

[lastchance]

#include <iostream>
#include <bitset>
#include <cstdint>
using namespace std;

using INT = uint8_t;

INT rrotate2( INT n )
{
   const INT fifteen = 15, seventeen = 17;
   return ( ( ( n & fifteen ) * seventeen ) >> 2 ) & fifteen;
}

int main()
{
   INT first = 2, second = 7;
   INT third = rrotate2( second );
   cout << "First:          " << bitset<4>( first  ) << '\n';
   cout << "Second:         " << bitset<4>( second ) << '\n';
   cout << "Second rotated: " << bitset<4>( third  ) << '\n';
   cout << "xor result:     " << bitset<4>( first ^ third ) << '\n';
}

[lastchance]

More general:

#include <iostream>
#include <bitset>
#include <cstdint>
using namespace std;

using INT = uint64_t;

int rrotate( int n, int bits, int shift )
{
   const INT ones = (1ul << bits) - 1;
   n &= ones;
   return ( ( ( n << bits ) + n ) >> shift ) & ones;
}

int main()
{
   int first = 2, second = 7;
   int third = rrotate( second, 4, 2 );
   cout << "First:          " << bitset<4>( first  ) << '\n';
   cout << "Second:         " << bitset<4>( second ) << '\n';
   cout << "Second rotated: " << bitset<4>( third  ) << '\n';
   cout << "xor result:     " << bitset<4>( first ^ third ) << '\n';
}

[Setat]

Thanks a lot Lastchance, for your smart solution.

[jonnin]

I came back to this one late to look at it from a less general side... specifically for 4 bit numbers, and came up with these. They duplicate the bits in a byte, that is, if you had a 4 bit number 1100 it would craft a byte holding 11001100. Then its just a matter of shifting down the correct amount and peeling off 4 the least significant 4 bits. (could apply & with 0b1111 to zero out the upper bits). If you only use 0-3 rotations the % can be removed for performance, but that relies on the user to do it.

unsigned char ror(unsigned char in, unsigned char num = 1)
{ //for 4 bit numbers only
	return (in<<4|in)>> num%4;
}

unsigned char rol(unsigned char in, unsigned char num = 1)
{ //for 4 bit numbers only
	return (in<<4|in)>> 4-num%4;
}


int main()
{
  unsigned char c = 1;//0b1100; 
 for(int i = 0; i < 8; i++)
  {
   c = rol(c); 
   cout << bitset<4>(c) << endl;
  }
}