1 Востаннє редагувалося reywwe95 (15.09.2016 20:04:36)

Тема: Бітові операції

Не маю уявлення як реалізувати 4 завдання
Як оптимізувати 5

#include "stdafx.h"
#include <iostream>
using namespace std;
int main()
{
    int value, kol = 1;
    cout << "Enter :" << endl;
    cin >> value;
    if (value % 2 == 1) {
        value = value - 1;
    }
    while (value % 2 == 0) {
        value = value / 2;
        kol++;
    }
    cout << "Kol = " << kol;
    system("pause");
    return 0;
}
Post's attachments

2016-09-15 17-26-57.JPG 116.89 kb, 94 downloads since 2016-09-15 

2

Re: Бітові операції

4 - просто порівнюєте кожен біт із 1, якщо 1 - збільшуєте лічільник. Як десяткові цифри з числа отримати, в курсі? Так от, двійкові (а біти - це ж двійкові цифри) - так само, тільки ділити всюди треба на 2.
5 - якщо число n є степенем двійки, то в двійковій формі воно виглядає ..., а n-1 виглядає як ... Таким чином, якщо застосувати до n і n-1 операцію ....
Думайте.

Подякували: FakiNyan1

3

Re: Бітові операції

в 5 пункті потрібно вікоритосувати тупу рекурсію

4

Re: Бітові операції

я б на вашому місці відмовився виконувати завдання надруковане москальською

Говоріть українською! Живіть українською! Відчувайте українською!

5

Re: Бітові операції

reywwe95 написав:

в 5 пункті потрібно вікоритосувати тупу рекурсію

типу ні, погляньте на степені двійки в двійковій формі, як вам порадив пан koala

Говоріть українською! Живіть українською! Відчувайте українською!

6

Re: Бітові операції

FakiNyan написав:

я б на вашому місці відмовився виконувати завдання надруковане москальською

Люблю російську мову і в універі виключно на ній викладають

7 Востаннє редагувалося reywwe95 (15.09.2016 21:32:04)

Re: Бітові операції

bool isPowerOfTwoRepresentable(unsigned int value) {
    return !(value&(value-1)) && !(value == 0);
}

  оптимізував 4 так і залишилось темним лісом

8 Востаннє редагувалося FakiNyan (15.09.2016 21:46:10)

Re: Бітові операції

reywwe95 написав:
bool isPowerOfTwoRepresentable(unsigned int value) {
    return !(value&(value-1)) && !(value == 0);
}

  оптимізував 4 так і залишилось темним лісом

Прихований текст
& зветься І не просто так.
ми приймаємо на вхід два біти, і ця операція повертає одиничку, якщо перший біт І другий біт являються одиничками. В іншому випадку повертається нуль.
А от вам пояснення, якщо ви так сильно лінуєтеся подивитись на двійкове представлення чисел
суть в тому, що всі степені двійки це одиничка з купою нулів
http://puu.sh/rclbk/3f90444cae.png

upd: а, це ви вже розібрались. Коми треба ставити!

Говоріть українською! Живіть українською! Відчувайте українською!

9 Востаннє редагувалося leofun01 (15.09.2016 22:55:55)

Re: Бітові операції

5:

bool isPowerOfTwoRepresentable(unsigned int value)
{
    return value && ((value - 1) & ~value) == value - 1;
}

4:

unsigned countSetBits(void *memory, unsigned bitsCount)
{
    unsigned count = 0,
        size = /*sizeof(void *) **/ 8,
        length = bitsCount / size,
        i = -1, j;
    while(++i < length)
    {
        j = -1;
        while(++j < size)
            count += (((char *)memory)[i] >> j) & 1;
    }
    j = -1;
    int end = bitsCount - length * size;
    while(++j < end)
        count += (((char *)memory)[i] >> j) & 1;
    return count;
}

10

Re: Бітові операції

А на StackOverflow радять bitset та різні красоти на кшталт

 unsigned int v; // count bits set in this (32-bit value)
 unsigned int c; // store the total here

 v = v - ((v >> 1) & 0x55555555);                    // reuse input as temporary
 v = (v & 0x33333333) + ((v >> 2) & 0x33333333);     // temp
 c = ((v + (v >> 4) & 0xF0F0F0F) * 0x1010101) >> 24; // count
Подякували: leofun011

11 Востаннє редагувалося -=ЮрА=- (18.09.2016 01:19:03)

Re: Бітові операції

Думаю це можна вважати за 1 рядок коду бо саме тіло power2 - 1 умова, тобто можна і тернарником записати

#include <cmath>
#include <iostream>
using namespace std;

size_t power2(size_t n);

int main(){
    cout<<pow(2.0, 5.0)<<" "<<power2(5)<<endl;
    cout<<pow(2.0, 17)<<" "<<power2(17)<<endl;
    return 0;
}


size_t power2(size_t n){
    if( n )
    return 2 << (n - 1);
    else
    return 1;
}

http://codepad.org/U2dOkNvB

32 32
131072 131072

12

Re: Бітові операції

По стандарту С зсув на 0 гарантовано коректний (не зсув).
Тому

size_t power2(size_t n) { return 1 << n; }
printf("Nested comments is %s\n", */*/**/"*/"/*"/**/ == '*' ? "OFF" : "ON");
Подякували: leofun011

13 Востаннє редагувалося ReAl (18.09.2016 04:19:52)

Re: Бітові операції

upd: Поведінка при від'ємному значенні кількості зсувів — «невизначена», реальні компілятори можуть відпрацювати коректно (але справедливо побурчати). Ніколи на це не розраховував :-)
Тим більше, що при зсуві на змінну, в яку занесено від'ємне значення, попередження не буде, а результат однак невизначений. На x86 швидше за все -1 буде сприйнято як FF, а зсув на число, більше за розмір операнда (теж невизначена поведінка) дасть 0.

http://cpp.sh/72yh

#include <iostream>
using namespace std;

#define TST(a) cout << #a << " = " << a << endl

int main()
{
    TST( (1<<0) );
    TST( (1<<1) );
    TST( (1<<16) );
    TST( (8<<-2) );
    return 0;
}

Бурчання

 In function 'int main()':
11:12: warning: left shift count is negative
4:39: note: in definition of macro 'TST' 

Вихід

(1<<0) = 1
(1<<1) = 2
(1<<16) = 65536
(8<<-2) = 2
printf("Nested comments is %s\n", */*/**/"*/"/*"/**/ == '*' ? "OFF" : "ON");
Подякували: leofun011

14 Востаннє редагувалося voland (20.09.2016 08:49:43)

Re: Бітові операції

ReAl написав:

На x86 швидше за все -1 буде сприйнято як FF, а зсув на число, більше за розмір операнда (теж невизначена поведінка) дасть 0.

Тут маленька ремарка - якщо ви використовуєте зсув знакового числа, меньш 0, і вправо, тоді завжди останнім числом буде -1 (0xFF), тому що знак розмажеться по всьому бітовому полю цього числа. Але це тільки зі знаковими, и тільки вправо.

Подякували: leofun011

15 Востаннє редагувалося ReAl (20.09.2016 12:50:10)

Re: Бітові операції

Про «буде сприйнято як FF» я писав про правий операнд оператора зсуву. По стандарту поведінка при цьому невизначена. Конкретно на x86 при вийманні правого операнда зі змінної буде використана команда зсуву з лічильником зсуву у 8-бітовому регістрі CL, там -1 буде сприйнято як FF, бо для асемблера цей операнд знаку не має. Тобто зсув таки у тому ж напрямку, а не у протилежному, але на дуже велике число і результат буде 0 (на іншій архітектурі може бути інший результат). Якщо ж правий операнд відомий на момент компіляції — приклад вище — компілятор побурчить, але правильно зсуне таки у протилежний бік. Саме тому навіть не implementation defined, а undefined.

Щодо лівого операнда, то ви не зовсім праві.
Стандарт каже, що для зсуву вправо при знаковому лівому операнді й при від'ємному значенні у ньому результат implementation defined, тобто для даних архітектури і компілятора завжди однаковий, але ніхто не гарантує, що це повториться на іншій платформі.
Тому так — мабуть, на всьому, з чим я зараз працюю, є команди асемблера для зсуву вправо з розмноженням старшого біта і при зсуві вправо від'ємні числа залишаються від'ємними.
Але я б на це не закладався, для знакових зсув використовую лише тоді, коли я точно знаю, що я роблю і навіщо.
До речі, для знакового-від'ємного числа навіть з розмноженням старшого біту зсув вправо на n бітів не еквівалентний діленню на 2n.

http://cpp.sh/9v2b

#include <iostream>
using namespace std;

#define TST(a) cout << #a << " = " << (a) << endl

int main()
{
    int a = -3;
    TST( a );
    TST( a >> 1 );
    TST( a / 2 );
    return 0;
}
a = -3
a >> 1 = -2
a / 2 = -1
printf("Nested comments is %s\n", */*/**/"*/"/*"/**/ == '*' ? "OFF" : "ON");
Подякували: voland1

16

Re: Бітові операції

-=ЮрА=- написав:

Думаю це можна вважати за 1 рядок коду бо саме тіло power2 - 1 умова, тобто можна і тернарником записати

#include <cmath>
#include <iostream>
using namespace std;

size_t power2(size_t n);

int main(){
    cout<<pow(2.0, 5.0)<<" "<<power2(5)<<endl;
    cout<<pow(2.0, 17)<<" "<<power2(17)<<endl;
    return 0;
}


size_t power2(size_t n){
    if( n )
    return 2 << (n - 1);
    else
    return 1;
}

http://codepad.org/U2dOkNvB

32 32
131072 131072

В п'ятому завданні сказано:
Реалізувати функцію, яка визначає можливість представлення value у вигляді 2n, де value - натуральне число.

Якщо розглядати це завдання строго так, як воно написане, то воно не коректне і тому не може бути виконаним.

Я посмів припустити, що це завдання має додаткові умови (по замовчуванню):
value і n мають один із стандартних типів (ushort, uint, ulong, ...), нехай int.

Тоді задача виглядає так:
Реалізувати функцію, яка поверне true, якщо для заданого value існує n таке, що виконується умова value = 2n, і яка поверне false в іншому випадку.

В стандартних типах value = 2n в двійковій системі виглядає завжди однаково:
000...0001000...000
або
/(0*)1(0*)/

Тобто вся задача зводиться до того, щоб перевірити чи в числі встановлено (1) лише один біт (решта - 0).
І виходить, що правильна відповідь:

bool isPowerOfTwoRepresentable(unsigned int value)
{
    return value && ((value - 1) & ~value) == value - 1;
}

Це я до того, що піднесення двійки в степінь - зовсім не те, що вимагається в завданні.

17 Востаннє редагувалося ReAl (20.09.2016 14:04:47)

Re: Бітові операції

leofun01 написав:
bool isPowerOfTwoRepresentable(unsigned int value)
{
    return value && ((value - 1) & ~value) == value - 1;
}

Щось тут забагато. value & (value-1) обнулює наймолодший «1»-ний біт змінної.
Тому (value & (value-1)) == 0 означає, що у змінній була максимум одна одиничка.
Тому досить

bool isPowerOfTwoRepresentable(unsigned int value)
{
    return value != 0                   // є хоча б одна одиничка
           && (value & (value-1)) == 0; // була максимум одна одиничка
}

Ну або компактним записом (наче вище щось подібне проскакувало)

bool isPowerOfTwoRepresentable(unsigned int value)
{
    return value && !(value & (value-1));
}
printf("Nested comments is %s\n", */*/**/"*/"/*"/**/ == '*' ? "OFF" : "ON");
Подякували: leofun01, voland2

18

Re: Бітові операції

Точно, варіант ReAl оптимальніший.

19

Re: Бітові операції

Та він не мій, це вже давно «надбання всього людства». Може, десь в глибинах груп usenet і можна знайти перших авторів.

printf("Nested comments is %s\n", */*/**/"*/"/*"/**/ == '*' ? "OFF" : "ON");
Подякували: koala, 0xDADA11C7, leofun013