Ladies_Man

Power of 2 Суммы степеней двойки

Dec 15th, 2013
142
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C 1.68 KB | None | 0 0
  1. #include <stdio.h>
  2.  
  3. int count;
  4.  
  5. int check_for_power_of_2 (int _value){
  6.         int v1 = _value;
  7.     if (v1 == 0) return 0;//0 точно не степень двойки
  8.     //циклически сдвигаем число вправо, пока не останется самая старшая единица
  9.  
  10.     while(v1 != 1) { //пока число больше единицы
  11.         if ((v1 & 1) != 0) return 0;//нашлась лишняя единица
  12.         v1 = v1 >> 1;//сдвиг
  13.     }
  14.     return 1;
  15. }
  16.  
  17. int main()
  18. {
  19.         int N, i;
  20.     scanf ("%d", &N);
  21.     int array[N];
  22.  
  23.         for (i = 0; i < N; i++) scanf("%d", &array[i]);
  24.  
  25.     int mask_value;
  26.     //делаем маску из единиц
  27.     unsigned int mask_limit = 0;
  28.     for (i = 0; i != N; i++)
  29.         mask_limit = mask_limit | (1 << i);
  30.  
  31.         count = 0;
  32.     //цикл от 0 до максимального значения числа
  33.     for (mask_value = 0; mask_value <= mask_limit; mask_value++){
  34.         int sum = 0;
  35.         int k = 0;
  36.         //каждое значение mask_value уникально
  37.         //след-но уникальна и последовательность нулей и единиц (из которых онро состоит)
  38.         for (k = 0; k != N; k++)
  39.             if (((mask_value >> k) & 1) == 1){//берем только единицы
  40.                 //берем числа (по индексу) из исходного массива
  41.                 //суммируем
  42.                 sum += array[k];
  43.                 //printf("%d+",array[k]);
  44.             }
  45.         //проверяем сумму на степень двойки
  46.         if (check_for_power_of_2(sum) == 1) {
  47.             //printf(" <power of two");
  48.             count++;
  49.         }
  50.         //printf("\n");
  51.     }
  52.         printf("%d", count);
  53.     return 0;
  54. }
Advertisement
Add Comment
Please, Sign In to add comment