Рекурсия в различных компиляторах

@diagon · Регистрация: 02.05.2010

Студворк — интернет-сервис помощи студентам

Доброго времени суток.
Задача: дано целое число n, нужно получить его битовое представление, развернуть его, и то, что получилось перевести обратно в десятичную систему счисления.
Пример:n = 4, ответ - 1
n = 6, ответ - 3.
Решил ее через циклы, прошла все тесты, поэтому решение меня не интересует.
Также написал красивую на мой взгляд рекурсию, которая отлично работает на gcc.

C++
1
2
3
4
5
6
7
8
9
10
#include <iostream>
#include <cmath>
int n, k;
int f(int n){
    return n ? f(n / 2) + n % 2 * pow(2., k++) : 0;
}
int main(){
    int n = 6;
    std::cout << f(n);
}

Но, VC++ этот код неправильно понимает(просто выводит назад это же число).
Собственно, вопрос - что в моей рекурсии неоднозначно? И как ее можно исправить?

@diagon · 28.07.2011, 10:41 **[ТС]**

Сообщение от ValeryS

а ниче что в памяти они все двоичные ???

Так вы на условие задачи посмотрите. Здесь более точный вариант условия. Перегнать число из десятичной в двоичную СС и обратно ничего не стоит, хекс здесь лишний.

Сообщение от ValeryS

а в процессоре ты тоже запретишь лишние разряды???

А при чем здесь процессор? Двоичную СС не только в нем можно использовать =)

Сообщение от ValeryS

если мне надо перевести 20 чисел я должен писать 20 программ?

Одну, но хорошую =)
Передо мной стояла задача не написать универсальную и читабельную программу, а решить простенькую задачу минимальным количеством символов. Среди цппшников я, в общем-то, первый.

ValeryS · 28.07.2011, 10:44

Сообщение от grizlik78

Но задача специфическая.

для переворота байта (слова ) достаточно распространенная удивляюсь что в стандартные библиотеки не встроили (или где то есть)?
но в таком варианте

Сообщение от diagon

0110 = 110
Реверснутый вариант - 011 = 11 = 3 в десятичной

потому получается

Сообщение от ValeryS

1,2,4,8 равно 1
3,6,С равно 3
7 Е равно 7

взял полубайты (вообше ответов куда больше)
я не знаю где она может пригодится

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

Сообщение от diagon

Перегнать число из десятичной в двоичную СС и обратно ничего не стоит

что значит перегнать???
вывести на экран(принтер)?

@diagon · 28.07.2011, 10:47 **[ТС]**

Сообщение от ValeryS

что значит перегнать

Получить массив нуликов/еденичек, который и нужно реверснуть, а потом реверснутый вариант перегнать обратно в десятичную СС.
Но со стеком рекурсии более красивое и короткое решение получается.

@ValeryLaptev · 28.07.2011, 15:50

При использовании глобальных переменных все гораздо проще получается:

C++
1
2
3
4
5
6
7
8
9
10
int k = 0;
 
int f(int d)
{ int b = d % 2;
  if(d > 0)
  { k = (k * 2 + b);
    int r = f(d/2); 
  }
  return k;   
}

И никаких pow()
Попробуйте без глобальных переменных - это гораздо интереснее...

@diagon · 28.07.2011, 15:55 **[ТС]**

Можно еще проще(ну во всяком случае короче):

C++
1
2
3
4
int n, k;
int f(int n){
    return n ? f(n / 2) + n % 2 * (1 << k++) : 0;
}

У паскалистов на 4 символа короче =(

@easybudda · 29.07.2011, 00:25

Не уверен, что правильно понял, но вот чего набыдлокодил...

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
#include <stdio.h>
#include <limits.h>
 
#define INT_BITS (CHAR_BIT * sizeof(int))
 
void bindump(unsigned val){
    int i = INT_BITS;
    
    while ( i )
        printf("%d", (val >> --i) & 1);
    printf("\n");
}
 
unsigned bit_reverse(unsigned val, size_t pos){
    return ( pos > 1 ) ? (bit_reverse(val, pos - 1) << 1) | ((val >> (pos - 1)) & 1) : val & 1;
}
 
int num_reverse(int num){
    return (int)bit_reverse((unsigned)num, INT_BITS);
}
 
int main(void){
    int num, rev;
    
    while ( printf("Number: ") && scanf("%d", &num) == 1 ){
        printf("DEC: %11d\tBIN: ", num);
        bindump(num);
        rev = num_reverse(num);
        printf("DEC: %11d\tBIN: ", rev);
        bindump(rev);
    }
    
    return 0;
}

@ValeryLaptev · 29.07.2011, 09:43

easybudda, да. Это хороший подход - реверсить строку битов.

@fasked · 29.07.2011, 12:22

Рекурсия это конечно здорово, но сам реверс битов делается вот так:

C
1
2
3
4
5
6
unsigned bitrev(unsigned x) {
   x = (x & 0x55555555) <<  1 | (x >>  1) & 0x55555555; 
   x = (x & 0x33333333) <<  2 | (x >>  2) & 0x33333333; 
   x = (x & 0x0F0F0F0F) <<  4 | (x >>  4) & 0x0F0F0F0F; 
   x = (x << 24) | ((x & 0xFF00) << 8) | ((x >> 8) & 0xFF00) | (x >> 24); 
   return x;

@ValeryLaptev · 29.07.2011, 12:51

fasked, здесь предполагается, что размер целого равен 32 битам, 4 байтам. Это не везде так...

При изменени размеров целого придется дописывать функцию. А в рекурсивной версии - нет.

@fasked · 29.07.2011, 13:19

Сообщение от ValeryLaptev

здесь предполагается, что размер целого равен 32 битам, 4 байтам. Это не везде так... При изменени размеров целого придется дописывать функцию. А в рекурсивной версии - нет.

Это да, но я не могу представить себе программы, где приходится заниматься реверсом битов и в которой заранее нет четкого представления о настолько низком уровне. То есть задача явно либо олимпиадная, либо для программирования каких-нибудь железяк, а уж там то все строго. Ну и конечно скорость и потребление памяти по сравнению с рекурсией.
То есть за все надо платить

@ValeryLaptev · 29.07.2011, 13:22

fasked, не... Вспомните big-endian и little-endian.

@fasked · 29.07.2011, 13:38

Сообщение от ValeryLaptev

Вспомните big-endian и little-endian.

Ну а разве это не низкий уровень? Есть четкая документация, как работает железка или спецификация протокола. Все следуют подобной документации и ... я не думаю, что возможны какие-либо значительные изменения в будущем, а введение дополнительного слоя абстракции легко позволит избежать проблем при появлении незначительных изменений.

Новые блоги и статьи Все статьи Все блоги /
Из невошедшего на форум (диалог с ИИ-гугла) zorxor 29.07.2026 А вот, что интересно, сказал мне ИИ-гугла: Этот текст — эмоциональный пост пользователя под ником zorxor на интернет-форуме (вероятно, посвященном мистике, непознанному или альтернативной науке). . . .	Был праздник вчера, а я и не знал. kumehtar 28.07.2026 27. 07. 2026г. Intel Core 2 Duo исполнилось 20 лет Новости компьютерного мира и их обсуждение (4) Салют, шампанское, овации! :drink:	Нейтральные знания, чистый код - бла-бла-бла-бла, на самом деле кликбейт и самореклама, плагиат, и вот почему Hrethgir 27.07.2026 То-есть отклонение такой публикации говорит само за себя, и пусть только возьмут на вооружение после отклонения публикации - это будет чистейшим актом плагиата. Отклонял Хабр. Дословно, отклонённая. . .	тв 16 бой ии anaschu 27.07.2026 Великий Перелом ИИ: Как уравнения ОДУ Radau дожали цензурные фильтры Алисы Фиксируем в мемофонде Теории Всего беспрецедентный факт в истории ИИ-зондирования. В затяжном многораундовом. . .
мв 15. непроверенное, возможно, глюк anaschu 27.07.2026 НАУЧНО-АНАЛИТИЧЕСКИЙ ОТЧЕТ. РАЗДЕЛ 1. 1: «НАУКА» (РАСШИРЕННАЯ СТЕХИОМЕТРИЧЕСКАЯ И ГЕНЕТИЧЕСКАЯ ВЕРСИЯ)Тема: Теоретическое обоснование инвариантности 19-мерного тензорного ядра непрерывных ОДУ и. . .	Очистка реквизитов и табличных частей документа при копировании (вариант 2) Maks 26.07.2026 Алгоритм из решения ниже разработан на примере нетипового документа "ЗаявкаНаРаботу", разработанного в КА2. Задача: Заменить алгоритм запрета копирования документов для сотрудников с ролью "Стажер",. . .	Доктрина интенционального знания - Доктрина для портала "Срез". Hrethgir 25.07.2026 Может найдётся кто захочет оценить доктрину. . . Написания правил участия для меня роскошь, требующая лимита времени, поэтому все сообщения не прошедшие модерацию будут видны только участникам портала,. . .	сукцессия 44. Решил подать на припринт в межународные сервисы препринтов. Но нужно одобрение от ученых anaschu 25.07.2026 Английский вариант. Пока кто то не одобрит мою личность, мне не получиться это опубликовать на препринте. Но заявку на публикацию статьи я сегодня подам.

@ValeryLaptev 1069 / 848 / 60 Регистрация: 30.04.2011 Сообщений: 1,659
	29.07.2011, 09:43
	easybudda, да. Это хороший подход - реверсить строку битов. 0

@ValeryLaptev 1069 / 848 / 60 Регистрация: 30.04.2011 Сообщений: 1,659
	29.07.2011, 12:51
	fasked, здесь предполагается, что размер целого равен 32 битам, 4 байтам. Это не везде так... При изменени размеров целого придется дописывать функцию. А в рекурсивной версии - нет. 0

@ValeryLaptev 1069 / 848 / 60 Регистрация: 30.04.2011 Сообщений: 1,659
	29.07.2011, 13:22
	fasked, не... Вспомните big-endian и little-endian. 0