How to cycle rotate left a binary string

Question

0.00/5 (No votes)

See more:

Okay the problem is to rotate left the bits of a binary string in a cyclic manner so that the MSB after 1 rotation comes to LSB.

for example if I input
10
The output will be
01

if input is
10101
output will be
01011
or simply
1011

Or if Input is
1
after rotate it stays
1

What I have tried:

C++

<pre>#include<bits/stdc++.h>
using namespace std;
#define INT_BITS 32
int performXOR(int x, int y) 
{ 
	return x^y; 
}
int leftRotate(int n, int d) 
{ 
    return (n << d)|(n >> (INT_BITS - d)); 
} 

int main(){
    
     int test;
    cin>>test;
    while(test--){
        
        long long a,b;
        int n;
        cin>>n;
        cin>>a>>b;
        cout<<performXOR(a,b)<<endl;
        a = leftRotate(a,2);
        cout << a << endl;
    }
    
    return 0;
    
}

Ignore the xor function here when i cycle rotate left (a)
for example input is 10
Then the Output i get is 40
Please advice on this one is much appreciated.
Also I'm new to coding
Really appreciate any sort of guidance
Thanks in Advance

Posted 8-Dec-19 5:41am

Md Razeenuddin Mehdi

Updated 9-Dec-19 1:50am

Add a Solution

Comments

Patrice T 8-Dec-19 11:51am

Which word you don't understand in 'binary string' ?

4 solutions

Solution 3

Try

C++

unsigned left_rotate( unsigned u )
{
  constexpr unsigned Bits = sizeof(u) * 8;

  if ( u == 0) return u;

  unsigned mask = 1 << (Bits-1); // mask has only the MSB set


  while ( (mask & u) == 0) // find the leading '1'
    mask >>= 1;

  u ^= mask;  // remove leading one
  u <<= 1; // left shift
  u |= 1; // put the removed one as LSB

  return u;
}

[update]
Full code, for testing it:

C++

#include <iostream>

unsigned left_rotate( unsigned u );
std::string to_binary( unsigned u);

int main()
{
  unsigned u;
  std::cout << "please enter an unsigned number " << std::endl;

  std::cin >> u;

  std::cout << "before left rotation " << to_binary(u) << " (" << u << ")" << std::endl;
  u = left_rotate( u );
  std::cout << "after  left rotation " << to_binary(u) << " (" << u << ")" << std::endl;
}

unsigned left_rotate( unsigned u )
{
  constexpr unsigned Bits = sizeof(u) * 8;
  if ( u == 0) return u;
  unsigned mask = 1 << (Bits-1); // mask has only the MSB set


  while ( (mask & u) == 0) // find the leading '1'
    mask >>= 1;

  u ^= mask;  // remove leading one
  u <<= 1; // left shift
  u |= 1; // put the removed one at the tail
  return u;
}

std::string to_binary(unsigned u)
{
  constexpr unsigned Bits = sizeof(unsigned)*8;
  constexpr unsigned Mask = 1 << (Bits-1);

  if ( u == 0) return "0";

  std::string str;

  unsigned n = 0;
  while ((u & Mask) == 0)
  {
    u <<= 1;
    ++n;
  }
  while ( n < Bits)
  {
    str += (u & Mask) == 0 ? '0' : '1';
    u <<= 1;
    ++n;
  }
  return str;
}

[/update]

Posted 8-Dec-19 23:17pm

CPallini

Updated 9-Dec-19 0:36am

v2

Comments

Richard MacCutchan 9-Dec-19 6:17am

What happens if the leftmost bit is a zero?

CPallini 9-Dec-19 6:29am

Leftmost bit is always 1 by definition (that is, I am assuming the input is a variable-lenght bit string), unless the number is 0.
I've posted full code for testing it, in my updated solution.

Richard MacCutchan 9-Dec-19 6:53am

The question implies that the number of bits to rotate can be of arbitrary length, which allows for the leftmost to be 0 or 1.

CPallini 9-Dec-19 6:59am

If you say 'arbitrary length' then there are two options, either
1. The leftmost '1' bit establishes the length of the bit string
or
2. You have to specify the length of the bit-string as input.
I've assumed (1).

Solution 1

A binary left shift is a shift operation not a rotate.

You first need to identify the leftmost bit and remove it, remembering it could be a zero or a one.
Next do the left shift operation of the remaining bits.
Finally add the saved bit in the rightmost position.

This is quite easy when operating on a full sized type (byte, short or int), but when it is an arbitrary number of bits you need to use some extra logic to capture the leftmost bit.

Posted 8-Dec-19 5:58am

Richard MacCutchan

Solution 4

You really need to learn the difference between numbers and their (readable) representations!

More importantly, you need to learn to read and understand requirements:
- the input is a binary string
- you need to (cyclic) rotate the digits of the binary string input
- cyclic rotation means that you need to move the MSB of the current input into the LSB position

To put this into code, you first need to read a binary string. So far you're not doing that - you're reading a decimal number:

C++

long long a;
cin >> a;

Sure, your compiler doesn't complain, and you won't get a runtime error either, when trying to read "10101". But your program will not do what you think it does! If you could inspect the memory of a, you'd see that the number stored there is '2775' if viewed as hexadecimal, or '10011101110101' if viewed as binary.

Likewise, if you read 10 as input, cin interprets it as a decimal number, and internally stores it as 'A' (hexadecimal) or '1010' (binary).

You need to understand that '10'(decimal), 'A'(hexadecimal) and '1010'(binary) are all the same number, just represented differently. And if you see one or the other representation, it doesn't mean the value is different, it means that the tool you use to view these values uses a different representation.

But, let's go back to the requirements: nothing in the requirement states that you have to actually store a number! All it says is that you should read a string, and manipulate that string. You could convert that string into the number that it represents, but that would serve no purpose: you are not required to do any numerical processing! In fact, you don't really need to care that (or if) you're dealing with a number!

This means you can simply use a string. And to remind you what this string is for, you can choose a meaningful name for it:

C++

std::string my_binary_number;
std::cin >> my_binary_number;

(I'm not a fan of using namespace std;, but that is not the point here)

As for rotating this string, it's not so hard to do. You can memorize the MSB:

C++

char MSB = my_binary_number[0];

and then you can remove the first digit and append the MSB at the end.

Check the member functions of std::string to learn how you can achieve this: string - C++ Reference[^]

If you want to remove leading '0's, that is not a problem either. Nor is printing the current state of the string. But if you need further help, feel free to ask.

Posted 9-Dec-19 1:51am

Stefan_Lang

Add a Solution

Add your solution here

Treat my content as plain text, not as HTML

Preview 0

…

Existing Members

Sign in to your account

...or Join us

Download, Vote, Comment, Publish.

Your Email
Password
Forgot your password?

Your Email
This email is in use. Do you need your password?
Optional Password

I have read and agree to the Terms of Service and Privacy Policy
Please subscribe me to the CodeProject newsletters

When answering a question please:

Read the question carefully.
Understand that English isn't everyone's first language so be lenient of bad spelling and grammar.
If a question is poorly phrased then either ask for clarification, ignore it, or edit the question and fix the problem. Insults are not welcome.
Don't tell someone to read the manual. Chances are they have and don't get it. Provide an answer or move on to the next question.

Let's work to help developers, not make them feel stupid.

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

OriginalGriff · Accepted Answer · 2019-12-08T06:13:00

A couple of things:
1) A "binary string" is not the same as an integer - it's an array of characters where each character can be a '0' or '1'. Rotating that is not the same thing as rotating an integer value at all.
2) Do notice that a shift is not the same as a rotate: C, C++, and even C# do not have a "binary rotate function" - they only have shift operators, which always move zeros into the newly vacated places and discard digits at the "other end". In other words, 0x0f shifted three places right will be 1, not 0x0f, or even 0xe0000001.

To rotate bits in the way you describe is more complex that your code shows: for 10 to become 01 requires you first finding the highest non-zero bit and using its location instead of a constant bits-in-an-integer value.