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

@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.

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

Новые блоги и статьи Все статьи Все блоги /
Часы с термометром и праздничным календарем yariko 12.11.2026 Сегодня мы рассмотрим как можно сделать отличные многофункциональные часы. Итак, поставим конкретную задачу: разработать часы с календарем, двумя термодатчиками, выводом поздравительных сообщений. . .	Транслитерация текста с кириллицы на латиницу (вариант №1) Maks 11.11.2026 Решил облегчить жизнь себе и коллегам админам при создании электронных почтовых ящиков для пользователей, в результате написал обработку "Транслитерация текста" с кириллицы на латиницу, а в ней. . .	Книги по геймдизайну, левел-дизайну, игровым механикам и проектированию игрового опыта 8Observer8 08.11.2026 Содержание блога \| English Version 1. 2003 - 06 - Designing Virtual Worlds (1st Edition) Автор: Richard A. Bartle \| Объем: 768 стр. Ссылки: Amazon . . .	Родители токсичные абьюзеры по отношению к своим детям ругают их оскорбляют не любят zorxor 08.11.2026 Жить в атмосфере постоянных оскорблений, критики и холодности со стороны родителей — это тяжелое и болезненное испытание, которое оставляет глубокие эмоциональные раны. Токсичное и абьюзивное. . .
Как только я захожу к себе в свою комнату я сразу же с себя снимаю свои трусы. Ответ от Джемени ИИ. zorxor 08.11.2026 Джемени, как только я захожу к себе в свою комнату я сразу же с себя снимаю свои трусы. Многие люди, возвращаясь домой, сразу переодеваются в максимально свободную одежду или вовсе предпочитают. . .	Паттерн очереди действий/команд (Action / Command Queue). Система очереди действий и кат-сцен с SDL3 Callbacks, cglm и OpenGL 8Observer8 07.11.2026 Содержание блога \| English Version Руководство для начинающих по реализации паттерна очереди действий/ команд (Action / Command Queue) на C++ (C++20) с использованием официального SDL3 Callbacks. . .	Проверка полного ФИО в типовом справочнике Maks 07.11.2026 Решение реализовано в конфигурации КА2, на примере справочника "КонтактныеЛицаПартнеров". Задача: Запрет инициалов. Не допускаеть использование сокращений вида "И. И. ", "И. И. ", "И И" и. . .	Про "Windows must die!" kumehtar 04.11.2026 Знаете, чет накатило. . . . Когда-то это было почти боевым кличем: мол, нормальный человек сидит на DOS, OS/ 2 или Linux, а вот это вот - Must Die. А теперь человек произносит «мастдай» с усмешкой - и. . .

@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