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

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

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

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

В программе обеспечить ввод исходных данных.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
18.03.2012, 15:26     Инвертирование группы бит.
Посмотрите здесь:

C++ Инвертирование строк в программе.
C++ инвертирование
C++ Инвертирование строки
Инвертирование текста C++
C++ Инвертирование содержимого файла
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
lemegeton
 Аватар для lemegeton
2910 / 1339 / 133
Регистрация: 29.11.2010
Сообщений: 2,720
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;
}
kerzh
0 / 0 / 0
Регистрация: 18.03.2012
Сообщений: 30
18.03.2012, 18:43  [ТС]     Инвертирование группы бит. #3
Это вот сами.
это да.
мы потоки еще не проходили. пока на примитивном уровне все. это для меня сложно
easybudda
Модератор
Эксперт С++
 Аватар для easybudda
9373 / 5423 / 914
Регистрация: 25.07.2009
Сообщений: 10,423
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;
}
lemegeton
 Аватар для lemegeton
2910 / 1339 / 133
Регистрация: 29.11.2010
Сообщений: 2,720
19.03.2012, 00:42     Инвертирование группы бит. #5
easybudda, хороший вариант. Без лишней информации.
Только зачем возводить двойку в степень через pow? Двойка в степень N же возводится сдвигом единицы влево 1 << N.
C
1
return x ^ (((1 << count) - 1) << pos);
Или я где-то не догоняю?
easybudda
Модератор
Эксперт С++
 Аватар для easybudda
9373 / 5423 / 914
Регистрация: 25.07.2009
Сообщений: 10,423
19.03.2012, 02:13     Инвертирование группы бит. #6
Цитата Сообщение от lemegeton Посмотреть сообщение
Двойка в степень N же возводится сдвигом единицы влево
В случае, если нужно инвертировать все биты, двойка в степени LONG_BIT выйдет за границу типа unsigned long, то есть вот так
C
1
invert(x, LONG_BIT, 0);
уже не вызовешь. А какой вариант хуже - отлавливать отдельно этот случай, или просто на него забить, я так и не решил...
Хотя похоже, зря я испугался, сейчас проверю...

Проверил, работает. Тогда, конечно, лучше без заморочек с pow().
fasked
Эксперт C++
 Аватар для fasked
4925 / 2505 / 180
Регистрация: 07.10.2009
Сообщений: 4,306
Записей в блоге: 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));
}
-=ЮрА=-
Заблокирован
Автор 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
Миниатюры
Инвертирование группы бит.  
-=ЮрА=-
Заблокирован
Автор 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;
}
- получаем число из нового строкового представления

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

Не по теме:

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

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

Не по теме:

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

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

Не по теме:

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

-=ЮрА=-
Заблокирован
Автор 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:За годы асм подзабыл, но обещаю в скором времени буду приводить "простенький код для начинающих" - уверен сейчас алгоритм стал на много понятней
Миниатюры
Инвертирование группы бит.  
-=ЮрА=-
19.03.2012, 17:55
  #15

Не по теме:

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

fasked
Эксперт C++
 Аватар для fasked
4925 / 2505 / 180
Регистрация: 07.10.2009
Сообщений: 4,306
Записей в блоге: 1
19.03.2012, 18:01     Инвертирование группы бит. #16
Цитата Сообщение от -=ЮрА=- Посмотреть сообщение

Не по теме:

- fasked, чем не сдвиг - сдвиг, главное понятно то как стало новичкам:cofee:

А самое смешное то, что алгоритм лучше не стал.
-=ЮрА=-
Заблокирован
Автор FAQ
19.03.2012, 18:08     Инвертирование группы бит. #17
fasked, а я и не говорил что он станет лучше - ты вёл речь о понятности и сдвигах или rol это не сдвиг?
Что является критерием нормальности? Я вот держу пари что за все предложенные коды преподаватель впаяет kerzh, пару, т.к. 100% по его фразе
Цитата Сообщение от kerzh Посмотреть сообщение
это да. мы потоки еще не проходили. пока на примитивном уровне все. это для меня сложно
- он ещё начинающий и в таком случае даже строковая маска сложна, так что прежде чем что то цеплять нужно ориентироваться на уровень автора темы а не на то как должно быть всё в идеале. Да без базара, я сейчас сразу инверт напишу в одной функции на асме и будет строк 5-6 кода и что это проще или лучше автору будет???
fasked
Эксперт C++
 Аватар для fasked
4925 / 2505 / 180
Регистрация: 07.10.2009
Сообщений: 4,306
Записей в блоге: 1
19.03.2012, 22:26     Инвертирование группы бит. #18
Цитата Сообщение от -=ЮрА=- Посмотреть сообщение
ты вёл речь о понятности и сдвигах или rol это не сдвиг?
Я не вел речи о понятности или сдвигах.
Цитата Сообщение от -=ЮрА=- Посмотреть сообщение
Да без базара, я сейчас сразу инверт напишу в одной функции на асме и будет строк 5-6 кода
Зачем?
Цитата Сообщение от -=ЮрА=- Посмотреть сообщение
Я вот держу пари что за все предложенные коды преподаватель впаяет kerzh, пару
Мне лично все равно, что ему там поставят. И по этой же причине я не собираюсь делать что-либо через одно место, особенно, если я это буду осознавать.
Цитата Сообщение от -=ЮрА=- Посмотреть сообщение
как должно быть всё в идеале
Так не бывает.
-=ЮрА=-
Заблокирован
Автор FAQ
19.03.2012, 22:58     Инвертирование группы бит. #19

Не по теме:

Цитата Сообщение от fasked Посмотреть сообщение
Мне лично все равно, что ему там поставят.
- странно думаю мы в ответе за тех кому написали, притом у тебя должность немного обязывает...

Цитата Сообщение от fasked Посмотреть сообщение
Да без базара, я сейчас сразу инверт напишу в одной функции на асме и будет строк 5-6 кода
Зачем?
- затем, что бысрей и лаконичней асемблерной вставки ничего не будет, а так просто шоб було



Добавлено через 3 минуты

Не по теме:

Цитата Сообщение от fasked Посмотреть сообщение
Я не вел речи о понятности или сдвигах.
- ну а я вёл о понятности алгоритма именно для автору темы вот и всё. Мне вообще по душе писать оконные MFC приложения а не чёрные досовские окна, но для лучшего понимания авторам тем пишу в консоли

MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
19.03.2012, 23:31     Инвертирование группы бит.
Еще ссылки по теме:

C++ Одинаковые группы букв и вывод их количества: переделать, чтобы находились абсолютно все группы
C++ Инвертирование строк
Инвертирование регистра символов C++

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

Или воспользуйтесь поиском по форуму:
easybudda
Модератор
Эксперт С++
 Аватар для easybudda
9373 / 5423 / 914
Регистрация: 25.07.2009
Сообщений: 10,423
19.03.2012, 23:31     Инвертирование группы бит. #20
Сообщение было отмечено автором темы, экспертом или модератором как ответ
А прерву-ка я эту милую беседу, пока до обсуждения распада образовательной системы на постсоветском пространстве не добрались. Примеров предоставили достаточное количество. Если понадобятся какие-то разъяснения, ТС, пишите - открою тему.

Добавлено через 24 минуты
В виде бонуса
C
1
2
3
4
5
6
7
8
9
10
11
/* Тупой вариант функции инвертирования битов. Чтобы концепцию не портить, никаких проверок допустимости параметров,
всё на совести вызывающей стороны */
unsigned long invert(unsigned long x, size_t count, size_t pos){
    size_t i;
    
    /* Незатейливо в цикле инвертируем биты. УжОс, никогда так не делайте! */
    for ( i = pos; i < pos + count; ++i )
        x ^= 1 << i;
    
    return x;
}
Yandex
Объявления
19.03.2012, 23:31     Инвертирование группы бит.
Закрытая тема Создать тему
Опции темы

Текущее время: 02:25. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru