Консультация № 180604
07.11.2010, 16:27
58.52 руб.
0 29 3
Здравствуйте
у меня есть задание на поразрядная обработка целых чисел на языке си. нужно определить, является ли симметричным двоичное представление целого числа N. обработку числа необходимо сделать без использования строк, только с помощью сдвигов, масок и битовых операций (&, | и т.д.). компилятор - visual c++ 6.0
у меня есть примерный алгоритм - создать две маски, установить их на концы числа и в цикле сдвигать их к середине, сравнивая биты. как реализовать этот алгоритм на языке си, я не знаю. помогите, пожалуйста

Обсуждение

давно
Профессор
230118
3054
07.11.2010, 16:45
общий
это ответ
Здравствуйте, Татьяна Львова!

Будем считать, что используем 32-битовый int.
Первая маска - 0x80000000. Для сдвига используем сдвиг вправо >>. Вторая маска первоначально равна 0x1.
Пусть число = n
В цикле 16 раз сравниваем n&m1 c n&m2
Вводим булеву переменную, которая определяет результат.
Код:

int n, i, m1=0x80000000, m2=0x1;
bool test=true;
printf("vvedite chislo\n");
scanf("%d", &n);
for(i=0;i<16;i++)
{
if((n&m1) != (n&m2))
{

test=false;
break;
}
m1>>=1;m2<<=1;
}
if (test==false)
printf("ne simmetrichno\n");
else
printf("simmetrichno\n");
5
Неизвестный
07.11.2010, 17:06
общий
Адресаты:
спасибо. а для 32битного n ,будет просто изменено условие цикла for(i=0;i<8;i++) на for(i=0;i<16;i++) или ещё что-то?

насколько я поняла, программа будет выглядеть так:

Код:

#include <stdio.h>
int n, i, m1=0x8000, m2=0x1;
bool test=true;

void main(void)
{
printf("vvedite chislo\n");
scanf("%d", n);

for(i=0;i<8;i++)
{
if(n&m1 != n&m1)
{
break;
test=false;
}
m1>>=1;m2<<=1;
}
if (test=false)
printf("ne simmetrichno\n");
else
printf("simmetrichno\n");
}


но так программа выдаёт предупреждение об ошибке (строка if(n&m1 != n&m1) ), запускается и выдаёт ошибку - "bit.exe - обнаружена ошибка, приложение будет закрыто"
давно
Профессор
230118
3054
07.11.2010, 17:11
общий
Запишите конъюнкции в скобках. (n&m1) != (n&m2)
Неизвестный
07.11.2010, 17:19
общий
Адресаты:
предупреждение исчезло, но программа всё равно вылетает после ввода проверяемого числа
давно
Профессор
230118
3054
07.11.2010, 17:21
общий
На каком шаге, можете выяснить?
Неизвестный
07.11.2010, 17:28
общий
Адресаты:
судя по всему, сразу же после ввода числа. мне кажется, это может быть как-то связано с размерностью числа. в visual studio 6 int занимает 4 байта (32 бита). возможно нужна другая маска
давно
Профессор
230118
3054
07.11.2010, 17:38
общий
Это ни при чем. В scanf надо указывать не переменную, а ее адрес.
scanf("%d", &n);
давно
Профессор
230118
3054
07.11.2010, 17:42
общий
if (test=false) Тоже ошибка. Происходит присваивание, результат всегда true
Проверка на равенство - (test==false) или проще (!test)
Неизвестный
08.11.2010, 09:28
общий
А числа 5 = 1012 и 9 = 10012 являются симметричными ?
давно
Профессор
230118
3054
08.11.2010, 10:02
общий
По данному алгоритму нет. Рассматривается все двоичное представление 32 битов.
Неизвестный
08.11.2010, 13:02
общий
10.11.2010, 17:02
это ответ
Здравствуйте, Татьяна Львова!
Еще можно так сделать.
5,3,6 и тому подобные числа будут симметричными.


Приложение:
#include <stdio.h>
int main()
{ /*можно подставить другой тип (в том числе свой собственный, определив требуемые операторы: ">>","&","!=")
Собственный тип только в виде структуры/массива фиксированной длины, иначе sizeof не будет работать правильно. Не класс!
например typedef unsigned mytype[10]; */
unsigned a=0;
int m=0,l=0,bits;
/*если поменять тип на unsigned long long, то формат будет %Lu,
для других типов тоже поменять соответственно*/
scanf("%u",&a);
bits=l=m=sizeof(a)*8-1;
/*Выведем число для проверки в двоичном виде*/
while(l>=0) {
printf("%d",(a>>(l--))&1);
};
printf("\n");
l=0;
/* Если нужно проверять симметричность в пределах ёмкости типа (32 bit, 64 bit и т.д.),
то следующий цикл нужно убрать */
/*отбрасываем нули слева */
while(m>0) {
if(((a >> m) & 1) != 0)
break;
--m;
};
/*сравниваем биты, двигаясь одновременно вниз от msb и вверх от lsb*/
while(m>l) {
if( ((a >> m) & 1) != ((a >> l) & 1) )
{
/*не совпали*/
printf("No\n");
return 0;
};
--m;
++l;
};
/*все совпали*/
printf("Yes\n");
return 0;
}
5
Неизвестный
08.11.2010, 13:05
общий
Цитата: 321399
А числа 5 = 1012 и 9 = 10012 являются симметричными ?

Добавил вариант, где будут. Дополнительно можно использовать любой тип для хранения числа, в том числе свой собственный, определив операторы (с++)
Неизвестный
08.11.2010, 14:45
общий
Почему бы не использовать логарифм для определения позиции msb ? Думаю от этого программа выиграет в читабельности.
Начальная позиция lsb по-моему всегда должна быть равна нулю, всё-таки число 1010 мало похоже на симметричное. К сожалению автор вопроса не привёл точного определения симметричности.
давно
Академик
320937
2216
08.11.2010, 15:27
общий
Добрый день!
Цитата: 321399
А числа 5 = 1012 и 9 = 10012 являются симметричными ?
Цитата: 321399
К сожалению автор вопроса не привёл точного определения симметричности.
Неизвестный
08.11.2010, 17:49
общий
Цитата: 321399
число 1010 мало похоже на симметричное

Если записать как 01010 то становится более похоже
Ваш вариант получится так:
Код:

--- t.c 2010-11-08 13:01:23.000000000 +0300
+++ t1.c 2010-11-08 17:45:26.000000000 +0300
@@ -21,18 +21,14 @@
/*считаем, что число дополнено слева нулями до требуемой длины
Если нужно проверять симметричность в пределах ёмкости типа (32 bit, 64 bit и т.д.), то 2 следующих цикла нужно убрать
*/
- /*отбрасываем нули слева и справа
+ /*отбрасываем нули слева
*/
while(m>0)
{
if(((a >> m) & 1) != 0)break;
--m;
};
- while(l<bits)
- {
- if(((a >> l) & 1) != 0)break;
- ++l;
- };
+
/*сравниваем биты, двигаясь одновременно вниз от msb и вверх от lsb*/
while(m>l)
{

Что значит использовать логарифм, не очень понятно (перевести в double, посчитать ln a/ln 2 - будет медленно и не эффективно).
Точно сказать, как правильнее не получится, так как
Цитата: 321399
автор вопроса не привёл точного определения симметричности.
Неизвестный
08.11.2010, 20:19
общий
Адресаты:
а как будут выглядеть маски m1=0x80000000 и m2=0x1 в двоичном виде?
давно
Профессор
230118
3054
08.11.2010, 21:42
общий
Единственная 1 в начале, остальные 0
Единственная 1 в конце, остальные 0
Неизвестный
09.11.2010, 08:02
общий
Цитата: 303901
Если записать как 01010 то становится более похоже

Согласен, надеюсь у преподавателя автора присутствует чувство юмора .
Неизвестный
09.11.2010, 19:08
общий
это ответ
Здравствуйте, Татьяна Львова!
Программа. C++. Компилировал GCC.
Код:
/* 
* File: main.cpp
* Author: Micren
*
* Created on 9 Ноябрь 2010 г., 17:44
*/

#include <limits>
#include <iostream>

using namespace std;

typedef unsigned int data_t;

/*
*
*/

// true если симметричное
bool isSymmetric(data_t value);
// В строку
string toBinaryString(data_t value);

int main()
{
while (true)
{
// Ввод числа
cout << "Введите целое положительное число:";
data_t val;
cin >> val;
if (cin.fail())
{
if (cin.eof())
{
break;
}
cin.clear();
cin.ignore(numeric_limits<streamsize>::max(), '\n');
cout << "Ошибочный ввод" << endl;
continue;
}
cout << "Число " << val << '(' << toBinaryString(val) << ") " << (isSymmetric(val) ? "" : "не ") << "симметричное" << endl;
}
return 0;
}

bool isSymmetric(data_t value)
{
data_t tmp = value, mirror = 0;
while (tmp)
{
mirror = (mirror << 1) | (tmp & 1);
tmp >>= 1;
}
return value == mirror;
}

string toBinaryString(data_t value)
{
string result;
do
{
result = "01"[value & 1] + result;
value >>= 1;
}
while (value);
return result;
}

Пример работы:
Код:
Введите целое положительное число:1
Число 1(1) симметричное
Введите целое положительное число:2
Число 2(10) не симметричное
Введите целое положительное число:-1
Число 4294967295(11111111111111111111111111111111) симметричное
Введите целое положительное число:101
Число 101(1100101) не симметричное
Введите целое положительное число:5
Число 5(101) симметричное


Программа на С.
Код:
/*
* File: main.cpp
* Author: Micren
*
* Created on 9 Ноябрь 2010 г., 17:44
*/

#include <stdlib.h>
#include <stdio.h>
#include <stdbool.h>

typedef unsigned int data_t;

#define DATA_BITS (sizeof (data_t) << 3)

/*
*
*/

// true если симметричное
bool isSymmetric(data_t value);
// Печать в двоичном виде
void printBinary(data_t value);

int main()
{
data_t val;
while (true)
{
// Ввод числа
printf("Введите целое положительное число:");
int ret = scanf("%u", &val);
if (ret != 1)
{
if (feof(stdin))
{
break;
}
printf("Ошибочный ввод\n");
return EXIT_FAILURE;
}
printf("Число %u(", val);
printBinary(val);
printf(") %s симметричное\n", isSymmetric(val) ? "" : "не");
}
return EXIT_SUCCESS;
}

bool isSymmetric(data_t value)
{
data_t tmp = value, mirror = 0;
while (tmp)
{
mirror = (mirror << 1) | (tmp & 1);
tmp >>= 1;
}
return value == mirror;
}

void printBinary(data_t value)
{
char buffer[DATA_BITS + 1] = {0}, *ptr = buffer + DATA_BITS;
do
{
*--ptr = "01"[value & 1];
value >>= 1;
}
while (value);
printf("%s", ptr);
}
Неизвестный
09.11.2010, 21:21
общий
а ваш вариант кода выдал мне, что число 4294868991 (11111111111111100111111111111111) несимметрично и число 4294721535 (11111111111111000011111111111111) тоже несимметрично, а вот числа 34 (00000000000000000000000000100010) и 4 (00000000000000000000000000000100) наоборот оказались симметричными. это конкретные примеры, были ещё другие числа, при которых рез-т был неверным


симметричность в моём задании - число в двоичном виде должно читаться одинаково слева до середины и справа до середины (пример симметричности - 100001, 110011 и т.д.)
Неизвестный
09.11.2010, 23:29
общий
Адресаты:
пользуясь вашим вариантом кода, я ни разу не получила в качестве результата "симметрично". все вводимые числа выдают рез-т "не симметрично". даже те, которые симметричны как например 10000000000000000000000000000001
Неизвестный
10.11.2010, 00:20
общий
В ответ добавил программу на C.
давно
Профессор
230118
3054
10.11.2010, 00:26
общий
Не учла разные разряды. Надо было писать
if((n&m1) != 0 && (n&m2)==0 ||(n&m1) == 0 && (n&m2)!=0)

Неизвестный
10.11.2010, 09:28
общий
Цитата: 318742
4294868991 (11111111111111100111111111111111) несимметрично

Это ошибка. Появилась, когда исправлял ошибку в цикле вывода числа. После вывода числа нужно добавить
Код:
l=0;


Цитата: 318742
симметричность в моём задании - число в двоичном виде должно читаться одинаково слева до середины и справа до середины (пример симметричности - 100001, 110011 и т.д

Вот теперь стало понятно, что требуется. К сожалению ответ уже отправил...
Собственно патч - исправление ошибки и приведение к вашим условиям:
Код:

--- t.c~ 2010-11-10 09:20:05.000000000 +0300
+++ t.c 2010-11-10 09:21:21.000000000 +0300
@@ -17,22 +17,17 @@
printf("%d",(a>>(l--))&1);
};
printf("\n");
-
- /*считаем, что число дополнено слева нулями до требуемой длины
- Если нужно проверять симметричность в пределах ёмкости типа (32 bit, 64 bit и т.д.), то 2 следующих цикла нужно убрать
+ l=0;
+ /*
+ Если нужно проверять симметричность в пределах ёмкости типа (32 bit, 64 bit и т.д.), то следующий цикл нужно убрать
*/
- /*отбрасываем нули слева и справа
+ /*отбрасываем нули слева
*/
while(m>0)
{
if(((a >> m) & 1) != 0)break;
--m;
};
- while(l<bits)
- {
- if(((a >> l) & 1) != 0)break;
- ++l;
- };
/*сравниваем биты, двигаясь одновременно вниз от msb и вверх от lsb*/
while(m>l)
{



Проверяем:
Код:

$ ./t
5
00000000000000000000000000000101
Yes
$ ./t
4294868991
11111111111111100111111111111111
Yes
$ ./t
4294721535
11111111111111000011111111111111
Yes
$ ./t
34
00000000000000000000000000100010
No

Неизвестный
10.11.2010, 10:43
общий
мне компилятор после исправления ошибок по-прежнему выдает, что 34 симметрично
Неизвестный
10.11.2010, 11:22
общий
Я могу исправить Ваш ответ, но, судя по
Цитата: 318742
мне компилятор после исправления ошибок по-прежнему выдает, что 34 симметрично

это ещё не последняя редакция?
Неизвестный
10.11.2010, 12:02
общий
Цитата: 318742
мне компилятор после исправления ошибок по-прежнему выдает, что 34 симметрично

Не может такого быть.
Вы патч накладывали программой или руками?
Если руками, то возможно не применилась эта часть:
Код:

- while(l<bits)
- {
- if(((a >> l) & 1) != 0)break;
- ++l;
- };

После патча должен получиться такой файл:
Код:
#include <stdio.h>

int main()
{
/*можно подставить другой тип (в том числе свой собственный, определив требуемые операторы: ">>","&","!=")
Собственный тип только в виде структуры/массива фиксированной длины, иначе sizeof не будет работать правильно. Не класс!
например typedef unsigned mytype[10];
*/
unsigned a=0;
int m=0,l=0,bits;
/*если поменять тип на unsigned long long, то формат будет %Lu, для других типов тоже поменять соответственно*/
scanf("%u",&a);
bits=l=m=sizeof(a)*8-1;
/*Выведем число для проверки в двоичном виде*/
while(l>=0)
{
printf("%d",(a>>(l--))&1);
};
printf("\n");
l=0;
/*
Если нужно проверять симметричность в пределах ёмкости типа (32 bit, 64 bit и т.д.), то следующий цикл нужно убрать
*/
/*отбрасываем нули слева
*/
while(m>0)
{
if(((a >> m) & 1) != 0)break;
--m;
};
/*сравниваем биты, двигаясь одновременно вниз от msb и вверх от lsb*/
while(m>l)
{
if( ((a >> m) & 1) != ((a >> l) & 1) )
{
/*не совпали*/
printf("No\n");
return 0;
};
--m;
++l;
};
/*все совпали*/
printf("Yes\n");
return 0;
}


34 не симметрично:
Код:
$ gcc -o t t.c
$ ./t
34
00000000000000000000000000100010
No
Неизвестный
11.11.2010, 20:51
общий
всё заработало, спасибо

а в строчке bits=l=m=sizeof(a)*8-1; зачем мы отнимаем единицу? sizeof(a) даст нам размер числа в байтах, умножая на 8 мы байты переводим в биты, а зачем отнимать единицу?
Неизвестный
12.11.2010, 12:05
общий
Цитата: 318742
зачем мы отнимаем единицу

Единица отнимается для получения смещения MSB. Например для 32-х разрядного числа старший бит находится по смещению 31, а младший по смещению 0. Чтобы получить значение старшего бита нужно выполнить сдвиг на 31 вправо и наложить маску 1.
Чтобы получить значение младшего бита нужно выполнить сдвиг на 0 вправо и наложить маску 1.
Иначе говоря обращение к последнему элементу массива выглядит так как то
char a[20];
char b=a[sizeof(a)-1];//предполагаем, что sizeof(char)==1 на используемой платформе
аналогично и при адресации отдельных битов.
Форма ответа