Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.71/7: Рейтинг темы: голосов - 7, средняя оценка - 4.71
11 / 11 / 2
Регистрация: 20.05.2011
Сообщений: 71
1

Побитовые сдвиги

11.07.2013, 19:49. Просмотров 1453. Ответов 5
Метки нет (Все метки)

Был на собеседовании, была задачка, вроде такая:

Есть функция, которая принимает char a (1 байт)
Нужно определить количество битов, установленных в 1 в этом байте.
Т.е., например, если а = '5', то ответ будет 2, т.к. 5 = 101.

Представлял как нужно сделать, но не смог написать...

Решать думал так:
1я итерация: сдвигаем вправо на 7 ( a >> 7 ), вправо на 0 (a << 0)
2я ит.: влево на 6, вправо на 1.
и т.д.
И при каждой итерации проверять на 1. есть она или нет.
Выходит если 5 = 0000 0101
1я ит.: 1
2я : 0
3я : 1
...

вот никак не могу реализовать. хрень все время какая-то получается. Помогите, плз.
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
11.07.2013, 19:49
Ответы с готовыми решениями:

Побитовые сдвиги
#include&lt;iostream&gt; int main() { int t=1; while(255&amp;t){ t=t&lt;&lt;t; std::cout&lt;&lt;t&lt;&lt;'\n';}...

Побитовые сдвиги
нужна помощь с заданием на С++: При написании функций можно использовать только следующее: -...

Программа на побитовые сдвиги
Привет! Выполнить путём сдвига вправо все биты, значение которых равно нулю и влево все биты,...

Как работают побитовые сдвиги?
Люди объясните плиз как работают побитовые сдвиги &lt;&lt; и &gt;&gt;, а то что то совсем запарился :confused:

5
Эксперт С++
4254 / 2228 / 203
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
11.07.2013, 19:52 2
самый простой способ, без извращений:
C++
1
2
3
4
5
6
7
8
9
10
11
int Count(char c)
{
   int i, count;
   for(i = cout = 0; i < 8; ++i)
   {
      if (c & 1)
         ++count;
      c >>= 1;
   }
   return count;
}
2
187 / 180 / 25
Регистрация: 27.01.2012
Сообщений: 1,335
11.07.2013, 19:52 3
razor_ua, эм, а как же делить на 2 чтобы перевести в дв. систему счисления?
0
415 / 414 / 72
Регистрация: 27.05.2012
Сообщений: 1,168
11.07.2013, 19:57 4
мне почему то первое пришло на ум побитовое или - то есть перебирать числа которые при побитовом или с исходным числом давали бы ноль - ну и отсюда найти количество единиц, только вот итераций будет куда больше ...
0
Эксперт С++
4254 / 2228 / 203
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
11.07.2013, 20:08 5
ну, напридумывать таких функций кучу можно:
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
#include<iostream>
 
// через итерацию
int Count1(char c, int n)
{
   int i, count;
   for(i = count = 0; i < n; ++i)
   {
      count += (c & 1);
      c >>= 1;
   }
   return count;
}
 
// через рекурсию (для неотрицательных чисел)
int Count2(unsigned char c)
{
   return c ? (c & 1) + Count2(c >> 1) : 0; 
}
 
// метод "разделяй и властвуй"
int Count3(char c, int l, int r)
{
   return l == r ? ((c >> l) & 1) : Count3(c, l, (l+r)/2) + Count3(c, (l+r)/2 + 1, r);  
}
 
// рекурсия для знаковых и беззнаковых чисел
int Count4(char c, int n)
{
   return n ? ((c >> (n-1)) & 1) + Count4(c, n - 1) : 0;    
}
 
int main()
{
   char c = 5;
   std::cout << Count1(c, sizeof(c)*8) << std::endl;
   std::cout << Count2(c) << std::endl;
   std::cout << Count3(c, 0, sizeof(c)*8 - 1) << std::endl;
   std::cout << Count4(c, sizeof(c)*8) << std::endl;
   return 0;
}
1
Jesus loves me
Эксперт С++
5110 / 3122 / 353
Регистрация: 12.12.2009
Сообщений: 7,899
Записей в блоге: 2
11.07.2013, 20:23 6
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
//types and constants used in the functions below
 
typedef unsigned __int64 uint64;  //assume this gives 64-bits
const uint64 m1  = 0x5555555555555555; //binary: 0101...
const uint64 m2  = 0x3333333333333333; //binary: 00110011..
const uint64 m4  = 0x0f0f0f0f0f0f0f0f; //binary:  4 zeros,  4 ones ...
const uint64 m8  = 0x00ff00ff00ff00ff; //binary:  8 zeros,  8 ones ...
const uint64 m16 = 0x0000ffff0000ffff; //binary: 16 zeros, 16 ones ...
const uint64 m32 = 0x00000000ffffffff; //binary: 32 zeros, 32 ones
const uint64 hff = 0xffffffffffffffff; //binary: all ones
const uint64 h01 = 0x0101010101010101; //the sum of 256 to the power of 0,1,2,3...
 
//This is a naive implementation, shown for comparison,
//and to help in understanding the better functions.
//It uses 24 arithmetic operations (shift, add, and).
int popcount_1(uint64 x) {
    x = (x & m1 ) + ((x >>  1) & m1 ); //put count of each  2 bits into those  2 bits 
    x = (x & m2 ) + ((x >>  2) & m2 ); //put count of each  4 bits into those  4 bits 
    x = (x & m4 ) + ((x >>  4) & m4 ); //put count of each  8 bits into those  8 bits 
    x = (x & m8 ) + ((x >>  8) & m8 ); //put count of each 16 bits into those 16 bits 
    x = (x & m16) + ((x >> 16) & m16); //put count of each 32 bits into those 32 bits 
    x = (x & m32) + ((x >> 32) & m32); //put count of each 64 bits into those 64 bits 
    return x;
}
 
//This uses fewer arithmetic operations than any other known  
//implementation on machines with slow multiplication.
//It uses 17 arithmetic operations.
int popcount_2(uint64 x) {
    x -= (x >> 1) & m1;             //put count of each 2 bits into those 2 bits
    x = (x & m2) + ((x >> 2) & m2); //put count of each 4 bits into those 4 bits 
    x = (x + (x >> 4)) & m4;        //put count of each 8 bits into those 8 bits 
    x += x >>  8;  //put count of each 16 bits into their lowest 8 bits
    x += x >> 16;  //put count of each 32 bits into their lowest 8 bits
    x += x >> 32;  //put count of each 64 bits into their lowest 8 bits
    return x & 0x7f;
}
 
//This uses fewer arithmetic operations than any other known  
//implementation on machines with fast multiplication.
//It uses 12 arithmetic operations, one of which is a multiply.
int popcount_3(uint64 x) {
    x -= (x >> 1) & m1;             //put count of each 2 bits into those 2 bits
    x = (x & m2) + ((x >> 2) & m2); //put count of each 4 bits into those 4 bits 
    x = (x + (x >> 4)) & m4;        //put count of each 8 bits into those 8 bits 
    return (x * h01)>>56;  //returns left 8 bits of x + (x<<8) + (x<<16) + (x<<24) + ... 
}
 
//This is better when most bits in x are 0
//It uses 3 arithmetic operations and one comparison/branch per "1" bit in x.
int popcount_4(uint64 x) {
    int count;
    for (count=0; x; count++)
        x &= x-1;
    return count;
}
не проверял, взял здесь.
2
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
11.07.2013, 20:23

Заказываю контрольные, курсовые, дипломные и любые другие студенческие работы здесь.

Сдвиги. (<< и >>)
Всем привет, подскажите плз, насчёт сдвигов, а то я чилал в инете и что то ничего не понял. Вот...

Сдвиги (С++)
Создать функцию, которая позволяет в заданном диапазоне натуральных чисел найти и выдать на экран...

Сдвиги
Необходимо сдвинуть массив беззнаковых целых чисел, как единое число. Обычные сдвиги и циклические...

Логические сдвиги
Вводим число 'k', где k=2n. Должно вывести 'n'. Решить при помощи логических сдвигов.

Циклические сдвиги
На этой неделе на уроках информатики Васе рассказывают про строки. Вчера Вася узнал, что такое...

циклические сдвиги
Как организовать циклический сдвиг числа? Например у меня есть число 5. В двоичной системе это...


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

Или воспользуйтесь поиском по форуму:
6
Ответ Создать тему
Опции темы

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