Форум программистов, компьютерный форум CyberForum.ru
Наши страницы

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
 
Рейтинг: Рейтинг темы: голосов - 19, средняя оценка - 4.89
kerzh
0 / 0 / 0
Регистрация: 18.03.2012
Сообщений: 30
#1

Инвертирование группы бит. - C++

18.03.2012, 15:26. Просмотров 2432. Ответов 19
Метки нет (Все метки)

Помогите с программой, пожалуйста.

Дана переменная типа long. Написать функцию, которая инвертирует группу из N разрядов переменной, начиная с разряда с номером P (где N и P - целые положительные числа, а нумерация разрядов числа начинается с нуля). Запрещается использование дополнительных переменных.

В программе обеспечить ввод исходных данных.
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
18.03.2012, 15:26
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Инвертирование группы бит. (C++):

Бит 8, младший и старший бит (по книге) - C++
Добрый день. Вот читаю книгу, и не пойму элементарной на первый взгляд вещи. Как понять следующие предложения: 1) Если бит...

переход с 32 бит на 64 бит - C++
Здравствуйте. Пробую на builder 10 перевести проект с 32 на 64 бит. Возникают странные ошибки: template <typename T> class DOT { ...

инвертирование - C++
Подскажите как инвертировать шестнадцатеричное число , но не всё , а первые 8-мь разрядов? Например х=df17?

Инвертирование текста - C++
Есть текст, например: Beautiful Explicit Simple Complex Я хочу его инвентировать по вертикале сначало, т. е. должно получится: ...

Инвертирование строки - C++
вот попробовал строку инвертировать, она инвертируется,но там еще мусор всякий,скажите как его убрать? #include <iostream> #include...

Инвертирование строк - C++
Надо все строки расположить в алфавитном порядке по убыванию и инвертировать каждую строку. С сортировкой я справился, а вот...

19
lemegeton
2925 / 1354 / 135
Регистрация: 29.11.2010
Сообщений: 2,725
18.03.2012, 18:06 #2
Цитата Сообщение от kerzh Посмотреть сообщение
В программе обеспечить ввод исходных данных.
Это вот сами.

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <iostream>
#include <string>
#include <limits>
 
std::string toBinary(unsigned long value, size_t bits =
  std::numeric_limits<unsigned long>::digits) {
  std::string result("");
  for (size_t i = 0; i < bits; ++i, value>>=1)
    result.insert(result.begin(), '0' + (value & 1));
  return result;
}
 
unsigned long invert(unsigned long value, size_t begin, size_t count) {
  return value ^ (std::numeric_limits<unsigned long>::max() >>
    (std::numeric_limits<unsigned long>::digits - count) << begin);
}
 
int main(int argc, char *argv[]) {
  unsigned long number = 817623877;
  std::cout << toBinary(number) << std::endl;
  std::cout << toBinary(invert(number, 1, 6)) << std::endl;
}
1
kerzh
0 / 0 / 0
Регистрация: 18.03.2012
Сообщений: 30
18.03.2012, 18:43  [ТС] #3
Это вот сами.
это да.
мы потоки еще не проходили. пока на примитивном уровне все. это для меня сложно
0
easybudda
Модератор
Эксперт CЭксперт С++
9683 / 5633 / 956
Регистрация: 25.07.2009
Сообщений: 10,811
18.03.2012, 19:05 #4
Лучший ответ Сообщение было отмечено автором темы, экспертом или модератором как ответ
C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include <stdio.h>
#include <limits.h>
#include <math.h>
 
#ifndef LONG_BIT
#define LONG_BIT ( sizeof(long) * CHAR_BIT )
#endif
 
char * binstr(const unsigned long x){
    static char buf[LONG_BIT + 1] = { 0 };
    size_t i = LONG_BIT;
    char * p = buf;
    
    while ( i-- )
        *p++ = '0' + ( ( x >> i ) & 1 );
    
    return buf;
}
 
unsigned long invert(unsigned long x, size_t count, size_t pos){
    return x ^ ( (unsigned long)(pow(2.0, (double)count) - 1.0) << pos );
}
 
int main(void){
    unsigned long x;
    size_t pos, count;
    
    while ( printf("Number: ") && scanf("%lu", &x) == 1 && printf("Count: ") && scanf("%u", &count) == 1 && printf("Pos: ") && scanf("%u", &pos) == 1 && pos + count <= LONG_BIT ){
        printf("Before: %lu\t%s\n", x, binstr(x));
        x = invert(x, count, pos);
        printf("After:  %lu\t%s\n", x, binstr(x));
    }
    
    return 0;
}
3
lemegeton
2925 / 1354 / 135
Регистрация: 29.11.2010
Сообщений: 2,725
19.03.2012, 00:42 #5
easybudda, хороший вариант. Без лишней информации.
Только зачем возводить двойку в степень через pow? Двойка в степень N же возводится сдвигом единицы влево 1 << N.
C
1
return x ^ (((1 << count) - 1) << pos);
Или я где-то не догоняю?
1
easybudda
Модератор
Эксперт CЭксперт С++
9683 / 5633 / 956
Регистрация: 25.07.2009
Сообщений: 10,811
19.03.2012, 02:13 #6
Цитата Сообщение от lemegeton Посмотреть сообщение
Двойка в степень N же возводится сдвигом единицы влево
В случае, если нужно инвертировать все биты, двойка в степени LONG_BIT выйдет за границу типа unsigned long, то есть вот так
C
1
invert(x, LONG_BIT, 0);
уже не вызовешь. А какой вариант хуже - отлавливать отдельно этот случай, или просто на него забить, я так и не решил...
Хотя похоже, зря я испугался, сейчас проверю...

Проверил, работает. Тогда, конечно, лучше без заморочек с pow().
0
fasked
Эксперт С++
4945 / 2525 / 180
Регистрация: 07.10.2009
Сообщений: 4,311
Записей в блоге: 1
19.03.2012, 11:23 #7
Ну и как вариант для массовки
C
1
2
3
4
unsigned long
invert(unsigned long x, unsigned long width, unsigned long offset) {
        return x ^ (~(0UL) << (LONG_BIT - width) >> (LONG_BIT - width - offset));
}
1
-=ЮрА=-
Заблокирован
Автор FAQ
19.03.2012, 13:09 #8
Цитата Сообщение от kerzh Посмотреть сообщение
Помогите с программой, пожалуйста.
Дана переменная типа long. Написать функцию, которая инвертирует группу из N разрядов переменной, начиная с разряда с номером P (где N и P - целые положительные числа, а нумерация разрядов числа начинается с нуля). Запрещается использование дополнительных переменных. В программе обеспечить ввод исходных данных.
- ниже простой алгоритм на плюсах работающий со строковым представлением бит, просто и наглядно
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
#include <iostream>
using namespace std;
 
int M = sizeof(long)*8;
char * getBits(long val)
{
    char * Bits = new char[M + 1];
    for(int i = 0; i < M; i++)
    {
        Bits[M - i - 1] = '0' + val % 2;
        val             = val / 2;
    }
    Bits[M] = '\0';
    return Bits;
}
 
char * invBits(char * Bits, int P, int N)
{
    for(int i = P, bit; i < P + N + 1; i++)
    {
        bit = Bits[M - i - 1] - '0';
        Bits[M - i - 1] = '0' + !bit;
    }
    return Bits;
}
 
long getNumFromBits(char * Bits)
{
    long pwr = 2;
    long val = (Bits[M - 1] - '0');
    for(int i = 1; i < M; i++)
    {
        val = val + pwr*(Bits[M - i - 1] - '0');
        pwr = pwr*2;
    }
    return val;
}
 
int main()
{
    int N, P;
    long val;
    char * Bits;
    cout<<"enter number : ";cin>>val;
    cout<<"enter N : ";cin>>N;
    cout<<"enter P : ";cin>>P;
    if(M < N + P + 1)
        cout<<"Chislo bitov k invertirovaniu prevoshodit razmer bitov v chisle\n";
    else
    {
        if(!(Bits = getBits(val)))
            cout<<"error get bit mask of number\n";
        else
        {
            cout<<"input  bits in number  : "<<Bits<<endl;
            Bits = invBits(Bits, P, N);
            cout<<"invert bits in number  : "<<Bits<<endl;
            val = getNumFromBits(Bits);
            cout<<"number with invert bits: "<<val<<endl;
            delete [] Bits;
        }
    }
    system("pause");
    return 0;
}
Код проверен http://codepad.org/CnANX3pa
0
Миниатюры
Инвертирование группы бит.  
-=ЮрА=-
Заблокирован
Автор FAQ
19.03.2012, 13:14 #9
kerzh, небольшие пояснения к коду
Цитата Сообщение от -=ЮрА=- Посмотреть сообщение
char * getBits(long val)
{
* * * * char * Bits = new char[M + 1];
* * * * for(int i = 0; i < M; i++)
* * * * {
* * * * * * * * Bits[M - i - 1] = '0' + val % 2;
* * * * * * * * val * * * * * * = val / 2;
* * * * }
* * * * Bits[M] = '\0';
* * * * return Bits;
}
- получаем строку представление двоичной записи числа
(помните что двоичная запись идёт задом наперёд от привычной нам записи слева направо - т.е. младшие разряды числа будут идти ближе к концу)

Цитата Сообщение от -=ЮрА=- Посмотреть сообщение
char * invBits(char * Bits, int P, int N)
{
* * * * for(int i = P, bit; i < P + N + 1; i++)
* * * * {
* * * * * * * * bit = Bits[M - i - 1] - '0';
* * * * * * * * Bits[M - i - 1] = '0' + !bit;
* * * * }
* * * * return Bits;
}
- инвертируем нужное нам число бит с заданной позиции

Цитата Сообщение от -=ЮрА=- Посмотреть сообщение
long getNumFromBits(char * Bits)
{
* * * * long pwr = 2;
* * * * long val = (Bits[M - 1] - '0');
* * * * for(int i = 1; i < M; i++)
* * * * {
* * * * * * * * val = val + pwr*(Bits[M - i - 1] - '0');
* * * * * * * * pwr = pwr*2;
* * * * }
* * * * return val;
}
- получаем число из нового строкового представления

Остальное в алгоритме крайне тривиально и думаю в пояснениях не нуждается...
0
fasked
19.03.2012, 14:33
  #10

Не по теме:

Цитата Сообщение от -=ЮрА=- Посмотреть сообщение
просто и наглядно
Звучит как "бесмысленно и беспощадно".

0
-=ЮрА=-
Заблокирован
Автор FAQ
19.03.2012, 14:41 #11
Цитата Сообщение от fasked Посмотреть сообщение
Звучит как "бесмысленно и беспощадно".
- лично мне на первом курсе всё что тут было приведено показалось бы именно
Цитата Сообщение от fasked Посмотреть сообщение
"бесмысленно и беспощадно"
. Я дал код в предположении кране скудных знаний у kerzh, вот и всё.

Не по теме:

PS:fasked, у меня что то неправильно посчиталось или не наглядно???

0
fasked
Эксперт С++
4945 / 2525 / 180
Регистрация: 07.10.2009
Сообщений: 4,311
Записей в блоге: 1
19.03.2012, 16:40 #12
Цитата Сообщение от -=ЮрА=- Посмотреть сообщение
Я дал код в предположении кране скудных знаний у kerzh, вот и всё.
Это то да. Просто переводить число в строку, чтобы работать с битами, это как-то странно В конце концов, надо же человека учить нормальным методам.
0
-=ЮрА=-
19.03.2012, 17:05
  #13

Не по теме:

fasked, сущность обучения - в постепенности осваиваемого материала, первокласнику не будет понятна производная, а 11 класнику не будет понятна теория поля с круговыми интегралами дивиргенциями и прочей вышкой, аналогично и здесь

0
-=ЮрА=-
Заблокирован
Автор FAQ
19.03.2012, 17:53 #14
fasked, всё я тебя понял и так будет на много проще
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
#include <iostream>
using namespace std;
 
int M = sizeof(long)*8;
char * getBits(char * Bits, long val)
{
    _asm
    {
        mov eax,val
        mov ebx,Bits
        mov ecx,32
        lop:
        rol eax,1
            jc m1
            mov [ebx],30h
            jmp m2
            m1:
            mov [ebx],31h
            m2:
            inc ebx
        loop lop
        mov [ebx],0
    }
    return Bits;
}
 
char * invBits(char * Bits, long val, int P, int N)
{
    val <<= (M - P + N);
    strrev(Bits);
    Bits = Bits + P;
    _asm
    {
        mov eax,val
        mov ebx,Bits
        mov ecx,N
        lopPN:
        rol eax,1
            jc mPN1
            mov [ebx],31h
            jmp mPN2
            mPN1:
            mov [ebx],30h
            mPN2:
            inc ebx
        loop lopPN
    }
    return strrev(Bits - P);
}
 
long getNumFromBits(char * Bits)
{
    long pwr = 2;
    long val = (Bits[M - 1] - '0');
    for(int i = 1; i < M; i++)
    {
        val = val + pwr*(Bits[M - i - 1] - '0');
        pwr = pwr*2;
    }
    return val;
}
 
int main()
{
    int N, P;
    long val;
    char * Bits = new char[M + 1];
    cout<<"enter number : ";cin>>val;
    cout<<"enter N : ";cin>>N;
    cout<<"enter P : ";cin>>P;
    if(M < N + P + 1)
        cout<<"Chislo bitov k invertirovaniu prevoshodit razmer bitov v chisle\n";
    else
    {
        cout<<"input  bits in number  : "<<getBits(Bits, val)<<endl;
        cout<<"invert bits in number  : "<<invBits(Bits, val, P, N)<<endl;
        cout<<"number with invert bits: "<<getNumFromBits(Bits)<<endl;
    }
    system("pause");
    return 0;
}
PS:За годы асм подзабыл, но обещаю в скором времени буду приводить "простенький код для начинающих" - уверен сейчас алгоритм стал на много понятней
0
Миниатюры
Инвертирование группы бит.  
-=ЮрА=-
19.03.2012, 17:55     Инвертирование группы бит.
  #15

Не по теме:

Цитата Сообщение от -=ЮрА=- Посмотреть сообщение
rol eax,1
- fasked, чем не сдвиг - сдвиг, главное понятно то как стало новичкам:cofee:

0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
19.03.2012, 17:55
Привет! Вот еще темы с ответами:

Инвертирование строк в программе. - C++
Внемлю вашей помощи, форумчане. Необходимо: &quot;7. Открыть файл, имя которого задается с клавиатуры. Создать новый файл, в который...

Инвертирование и циклический сдвиг - C++
Задание: Если содержание принятого кода может быть представлено в виде 2 в степени n, то выполнить операцию инвертирования значимых бит с...

Инвертирование регистра символов - C++
char str; cin.getline(str,n); for(int i=0;i&lt;strlen(str);i++){ if(islower(str)){ str=toupper(str); ...

Инвертирование содержимого файла - C++
Здравствуйте! Скажите как модно реализовать инвертирование содержимого файла! Причем нужно инвертировать не по одному символу, а целыми...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
15
19.03.2012, 17:55
Закрытая тема Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru