Programowanie i algorytmy

Suma bitów danej liczby

Zad. 4. Napisz funkcję, która zwróci prawdę, w przypadku, gdy suma cyfr danej liczby, oraz suma cyfr tej liczby w notacji binarnej będzie taka sama, oraz:

a) wyświetli wszystkie takie liczby z przedziału <n, m>, gdzie n i m podajemy z klawiatury, które spełniają kryteria zadania.

Zrealizuj to zadanie za pomocą trzech funkcji:

  • funkcji zwracającej sumę cyfr w systemie dziesiętnym
  • funkcji zwracającej sumę cyfr w systemie binarnym
  • funkcji zwracającej prawdę lub fałsz, w zależności ok spełnienia kryteriów

Wejście

Liczba całkowita mieszcząca się w zmiennej typu long long.


Wyjście

Komunikat określający, czy dana liczba spełnia kryteria zadania, oraz sumy cyfr w odpowiednich systemach.

 

 

Rozwiązanie

Aby wyłuskać cyfry danej liczby w systemie dziesiętnym postępujemy zgodnie z zasadą:

{tex}cyfra = liczba\ mod\ 10{/tex}

{tex}liczba = liczba\ div\ 10{/tex}

Np. dla liczby 123 mamy:

{tex}cyfra = 123\ mod\ 10 = 3{/tex}

{tex}123\ div\ 10 = 12{/tex}

Podaną czynność wykonujemy do momentu, gdy liczba osiągnie wartość 0, gdzie

mod - reszta z dzielenia
div - dzielenie całkowite.

Dla systemu binarnego postępujemy analogicznie podstawiając zamiast 10 liczbę 2.

Sposób drugi dla systemu binarnego wykonuje się według następującej idei:

cyfra = liczba & 1;

liczba = liczba >>1;

Aby wyłuskać ostatnią cyfrę, wystarczy wykonać działanie (operacje bitowe):

 

  1001101
  1
& 0000001

 

Gdy ostatni bit jest równy 1, to działanie 1 & 1 = 1, natomiast gdy ma wartość 0, to mamy 0 & 1 = 0, w ten sposób uzyskujemy ostatni bit danej liczby.

Aby skrócić liczbę o jeden bit, należy przesunąć ją w prawą stronę o 1 za pomocą operatora ">>". Popatrzmy na przykład:

 

(1000111110)2 >> 1 = (100011111)2

 

Rozwiązanie w C++
#include <iostream>
#include <cstdlib>
 
using namespace std;
 
int suma_dec(long long liczba)
{
  int s=0;
 
  while(liczba>0)
  {
    s+=liczba%10;
    liczba/=10;
  }
return s;
}
 
//pierwszy sposób
int suma_bin_1(long long liczba)
{
  int s=0;
 
  while(liczba>0)
  {
    s+=liczba%2;
    liczba/=2;
  }
return s;
}
 
//drugi sposób za pomocą operatorów bitowych
int suma_bin_2(long long liczba)
{
  int s=0;
 
  while(liczba>0)
  {
    s+=liczba&1;
    liczba>>=1;
  }
 
return s;
}
 
bool czy_rowne(int a,int b)
{
//jeśli a jest równe b to zwraca wartość true i wychodzi z funkcji
  if(a==b)return true; 
 
  return false;
}
 
int main()
{
 
  long long liczba;
  char opcja;
 
  do{  
    system("cls"); //czyszczenie ekranu
 
    cout<<"Podaj liczbę: ";
    cin>>liczba;
    cout<<endl;
 
    if(czy_rowne(suma_bin_2(liczba),suma_dec(liczba)))
      cout<<"Liczba "<<liczba<<" spełnia kryteria zadania";
    else
      cout<<"Liczba "<<liczba<<" nie spełnia kryteria zadania";
 
    cout<<endl<<endl;
 
    cout<<"Suma cyfr w systemie binarnym: "<<suma_bin_2(liczba)<<endl;
    cout<<"Suma cyfr w systemie dziesiętnym: "<<suma_dec(liczba)<<endl;
 
    cout<<endl;
 
    cout<<"Aby zakończyć wciśnij q, w przeciwnym razie dowolny znak ";
 
    cin>>opcja;
 
  }while(opcja!='q'); //po wciśnięciu q program kończy działanie
 
return 0;
}