Md Razeenuddin Mehdi Ответов: 4

Как циклически вращать левую двоичную строку

Итак, проблема состоит в том, чтобы повернуть влево биты двоичной строки циклическим образом так, чтобы MSB после 1 поворота пришел к LSB.

например, если я ввожу
10
Выход будет таким
01

если вход есть
10101
выход будет таким
01011
или просто
1011

Или если вход есть
1
после поворота он остается
1

Что я уже пробовал:

<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;
    
}


Игнорируйте функцию xor здесь, когда я циклически поворачиваюсь влево (a)
например входной сигнал равен 10
Тогда выход, который я получаю, равен 40
Пожалуйста, совет по этому вопросу очень ценится.
Кроме того я новичок в программировании
Очень ценю любое руководство
заранее спасибо

Patrice T

Какое слово вы не понимаете в "двоичной строке"?

4 Ответов

Рейтинг:
2

CPallini

Попробуй

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;
}




[обновление]
Полный код, для его тестирования:
#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;
}

[/обновление]

Richard MacCutchan

Что произойдет, если крайний левый бит равен нулю?

CPallini

Крайний левый бит всегда есть 1 по определению (то есть я предполагаю, что входные данные представляют собой битовую строку переменной длины), если только число не является 0.
Я опубликовал полный код для его тестирования в своем обновленном решении.

Richard MacCutchan

Вопрос подразумевает, что число битов для поворота может быть произвольной длины, что позволяет крайнему левому быть равным 0 или 1.

CPallini

Если вы говорите "произвольная длина", то есть два варианта, либо
1. самый левый бит '1' устанавливает длину битовой строки
или
2. Вы должны указать длину битовой строки в качестве входных данных.
Я предположил (1).

Рейтинг:
2

Stefan_Lang

Вам действительно нужно узнать разницу между числами и их (читаемыми) представлениями!

Что еще более важно, вам нужно научиться читать и понимать требования:
- входные данные являются двоичными строка
- вам нужно (циклически) вращать цифры двоичного кода строка вход
- циклическое вращение означает, что вам нужно переместить MSB текущего входа в положение LSB

Чтобы поместить это в код, вам сначала нужно прочитать двоичный файл строка Пока что вы этого не делаете - Вы читаете десятичное число: 

long long a;
cin >> a;

Конечно, ваш компилятор не жалуется, и вы также не получите ошибку времени выполнения, когда попытаетесь прочитать "10101". Но ваша программа не будет делать то, что вы думаете, что она делает! Если бы вы могли проверить память, вы увидите, что числа, хранящегося там '2775' если, рассматривается как шестнадцатеричное, или '10011101110101' если рассматривать как двоичные.

Аналогично, если вы читаете 10 в качестве входных данных, cin интерпретирует его как десятичное число и внутренне сохраняет его как "A" (шестнадцатеричное) или "1010" (двоичное).

Вы должны понимать, что " 10 "(десятичная), " а "(шестнадцатеричная) и "1010" (двоичная) - это одно и то же число, просто представленный иначе. И если вы видите одно или другое представление, это не означает, что значение отличается, это означает, что инструмент, который вы используете для просмотра этих значений, использует другое представление.



Но вернемся к требованиям: ничто в требовании не говорит о том, что вы должны на самом деле хранить число! Все, что он говорит, это то, что вы должны прочитать строку и манипулировать этой строкой. Вы мог преобразуйте эту строку в число, которое она представляет, но это не будет служить никакой цели: вы не обязаны выполнять какую-либо числовую обработку! На самом деле, вам не нужно беспокоиться о том, что (или если) вы имеете дело с числом!

Это означает, что вы можете просто использовать строку. И чтобы напомнить вам, для чего предназначена эта строка, вы можете выбрать для нее осмысленное имя:
std::string my_binary_number;
std::cin >> my_binary_number;
(Я не являюсь поклонником using namespace std; но дело здесь не в этом)

Что касается вращения этой струны, то это не так уж трудно сделать. Вы можете запомнить MSB:
char MSB = my_binary_number[0];
а затем вы можете удалить первую цифру и добавить MSB в конце.

Проверьте функции-члены std::string, чтобы узнать, как вы можете этого добиться: строка - ссылка на C++ [^]

Если вы хотите удалить ведущие '0, это тоже не проблема. Также не выполняется печать текущего состояния строки. Но если вам нужна дополнительная помощь, не стесняйтесь спрашивать.

Рейтинг:
18

OriginalGriff

Есть пара вещей:
1) "двоичная строка" - это не то же самое, что целое число-это массив символов, где каждый символ может быть " 0 " или "1". Вращение-это совсем не то же самое, что вращение целочисленного значения.
2) Обратите внимание, что сдвиг - это не то же самое, что поворот: C, C++ и даже C# не имеют "двоичной функции поворота" - у них есть только операторы сдвига, которые всегда перемещают нули во вновь освобожденные места и отбрасывают цифры на "другом конце". Другими словами, 0x0f, сдвинутый на три места вправо, будет равен 1, а не 0x0f или даже 0xe0000001.

Чтобы повернуть биты так, как вы описываете, это более сложно, чем показывает ваш код: для того, чтобы 10 стало 01, требуется сначала найти самый высокий ненулевой бит и использовать его местоположение вместо постоянного значения бит-в-целочисленном значении.

Richard MacCutchan

0x0f сдвинутый на три места влево будет равен 1
Неужели?

OriginalGriff

Исправлено - и большие буквы "Л" И "р" были нарисованы на моих ботинках, на всякий случай ...

Md Razeenuddin Mehdi

Хорошо, спасибо за совет, я попробую поместить a[0] в строку во временной переменной, вручную сдвинуть остальные биты влево, а затем поместить a[0] в последний индекс.

Рейтинг:
1

Richard MacCutchan

Двоичный сдвиг влево-это операция сдвига, а не поворота.

Сначала вам нужно определить крайний левый бит и удалить его, помня, что это может быть ноль или единица.
Затем выполните операцию сдвига влево оставшихся битов.
Наконец, добавьте сохраненный бит в крайнее правое положение.

Это довольно просто при работе с полноразмерным типом (byte, short или int), но когда это произвольное количество битов, вам нужно использовать некоторую дополнительную логику для захвата самого левого бита.