Kalkulator IP

Witam
Rzowiązuje zadanie Kalkulator IP (http://pl.spoj.pl/problems/MWP2_1B/) ze SPOJa.
Napisałem taki kod:

 #include<iostream>
using namespace std;
int d, ip, i0, b1, b2, b3, b4, s1, s2, s3, s4, wart[32], il;
bool host[32], maska[32], siec[32], broadcast[32];
int main()
{
    wart[0]=1;
    for(i0=1; i0<=31; i0++) wart[i0]=wart[i0-1]*2;
    cin >> d;
    for(int i=0; i<d; i++)
    {
            cin >> ip;
            i0=7;
            do
            {
                if(ip%2==1) host[i0]=1; else host[i0]=0;
                ip/=2;
                i0--;
            } while(ip>0);
            cin >> ip;
            i0=15;
            do
            {
                if(ip%2==1) host[i0]=1; else host[i0]=0;
                ip/=2;
                i0--;
            } while(ip>0);
            cin >> ip;
            i0=23;
            do
            {
                if(ip%2==1) host[i0]=1; else host[i0]=0;
                ip/=2;
                i0--;
            } while(ip>0);
            cin >> ip;
            i0=31;
            do
            {
                if(ip%2==1) host[i0]=1; else host[i0]=0;
                ip/=2;
                i0--;
            } while(ip>0);
            cin >> ip;
            i0=7;
            do
            {
                if(ip%2==1) maska[i0]=1; else maska[i0]=0;
                ip/=2;
                i0--;
            } while(ip>0);
            cin >> ip;
            i0=15;
            do
            {
                if(ip%2==1) maska[i0]=1; else maska[i0]=0;
                ip/=2;
                i0--;
            } while(ip>0);
            cin >> ip;
            i0=23;
            do
            {
                if(ip%2==1) maska[i0]=1; else maska[i0]=0;
                ip/=2;
                i0--;
            } while(ip>0);
            cin >> ip;
            i0=31;
            do
            {
                if(ip%2==1) maska[i0]=1; else maska[i0]=0;
                ip/=2;
                i0--;
            } while(ip>0);
            for(i0=0; i0<32; i0++)
            {
                      broadcast[i0]=host[i0] | (!maska[i0]);
                      siec[i0]=maska[i0] & host[i0];
            }
            
            if(broadcast[31]) b4+=1;
            if(broadcast[30]) b4+=2;
            if(broadcast[29]) b4+=4;
            if(broadcast[28]) b4+=8;
            if(broadcast[27]) b4+=16;
            if(broadcast[26]) b4+=32;
            if(broadcast[25]) b4+=64;
            if(broadcast[24]) b4+=128;
            
            if(broadcast[23]) b3+=1;
            if(broadcast[22]) b3+=2;
            if(broadcast[21]) b3+=4;
            if(broadcast[20]) b3+=8;
            if(broadcast[19]) b3+=16;
            if(broadcast[18]) b3+=32;
            if(broadcast[17]) b3+=64;
            if(broadcast[16]) b3+=128;
            
            if(broadcast[15]) b2+=1;
            if(broadcast[14]) b2+=2;
            if(broadcast[13]) b2+=4;
            if(broadcast[12]) b2+=8;
            if(broadcast[11]) b2+=16;
            if(broadcast[10]) b2+=32;
            if(broadcast[9]) b2+=64;
            if(broadcast[8]) b2+=128;
            
            if(broadcast[7]) b1+=1;
            if(broadcast[6]) b1+=2;
            if(broadcast[5]) b1+=4;
            if(broadcast[4]) b1+=8;
            if(broadcast[3]) b1+=16;
            if(broadcast[2]) b1+=32;
            if(broadcast[1]) b1+=64;
            if(broadcast[0]) b1+=128;
            
            if(siec[31]) s4+=1;
            if(siec[30]) s4+=2;
            if(siec[29]) s4+=4;
            if(siec[28]) s4+=8;
            if(siec[27]) s4+=16;
            if(siec[26]) s4+=32;
            if(siec[25]) s4+=64;
            if(siec[24]) s4+=128;
            
            if(siec[23]) s3+=1;
            if(siec[22]) s3+=2;
            if(siec[21]) s3+=4;
            if(siec[20]) s3+=8;
            if(siec[19]) s3+=16;
            if(siec[18]) s3+=32;
            if(siec[17]) s3+=64;
            if(siec[16]) s3+=128;
            
            if(siec[15]) s2+=1;
            if(siec[14]) s2+=2;
            if(siec[13]) s2+=4;
            if(siec[12]) s2+=8;
            if(siec[11]) s2+=16;
            if(siec[10]) s2+=32;
            if(siec[9]) s2+=64;
            if(siec[8]) s2+=128;
            
            if(siec[7]) s1+=1;
            if(siec[6]) s1+=2;
            if(siec[5]) s1+=4;
            if(siec[4]) s1+=8;
            if(siec[3]) s1+=16;
            if(siec[2]) s1+=32;
            if(siec[1]) s1+=64;
            if(siec[0]) s1+=128;
            
            i0=31;
            do i0--; while(!maska[i0]);
            i0=32-i0;
            if(host[0] && host[1] && host[2]) il=0; else il=wart[i0-1]-2;
            cout << il << "\n";
            if(il!=0) cout << s1 << "." << s2 << "." << s3 << "." << s4+1 << " " << b1 << "." << b2 << "." << b3 << "." << b4-1 << "\n";
            b1=0;
            b2=0;
            b3=0;
            b4=0;
            s1=0;
            s2=0;
            s3=0;
            s4=0;
            for(i0=0; i0<=31; i0++)
            {
                      maska[i0]=0;
                      host[i0]=0;
                      siec[i0]=0;
                      broadcast[i0]=0;
            }
    }

}

Niestety odpowiedź jest zła. Szukam błędu już jakiś czas ale niestety nie mogę znaleźć :)
Wyliczam adres sieci i broadcast. Jako adres pierwszego hostu wyświetlam adres sieci ze zwiększonym o 1 ostatnim oktecie adresu sieci, a jako ostatni adres wyświetlam broadcast ze zmniejszonym o jeden ostatnim oktetem. Licze też ile bitów w masce jest równych 0 i na tej podstawie wyliczam ilośc hostów w sieci (2^ilość_bitów_zerowych - 2). Dodatkowa dla klas D i E adresów IP (pierwsze 3 bity adresu hosta równe 111) wypisuje zero hostów. Mimo to program nie działa tak jak należy.

Za znalezienie błędu będę bardzo wdzięczny

Pozdrawiam

if(siec[31]) s4+=1;
            if(siec[30]) s4+=2;
            if(siec[29]) s4+=4;
            if(siec[28]) s4+=8;
            if(siec[27]) s4+=16;
            if(siec[26]) s4+=32;
            if(siec[25]) s4+=64;
            if(siec[24]) s4+=128;

Co do postu się nie wypowiadam, ale to wygląda tragicznie. Dlaczego nie użyjesz for'a?

To tylko tak roboczo. Jak już program będzie działał dobrze to napisze bardziej czytelny kod :)

@anorbia natychamiast skasuj ten kod i napisz jeszcze raz. Tym razem jak normalny człowiek, korzystając z pętli, zapewne w ~30 linijkach.

ubuntuser napisał(a):

Dlaczego nie użyjesz for'a?

for dla pojedynczej operacji podnoszenia (2 do potegi n)?
ilosc adresow (dla ipv4) (2^(32-ilosc bitow maski))-2 (2 bo broadcast i adres sieci)

adres broadcast to ip|(~mask)
adrs sieci to ip&mask

Nie musisz sie trzymac porządku sieciowego (big andian), możesz swobodnie ip i maske wciagac do long inta (((1bajt)<<8)+2bajt)<<8...

jezu 30 linijek na całośc? po co aż tyle?

kwestia tego jak potraktujesz siec z maska 31 i 32 bit, czy ma adrs uzywalny, czy tez go nie ma

wyrażenie 1<<n daje n-tą potegę 2

To zaraz zmienie kod :)

Ilość adresów, broadcast i adres sieci liczę tak jak napisał @flabra Dla masek 31 i 32 bitowych dawałem odpowiedź 0 adresów (wtedy jest tylko adres sieci i broadcast?)

Brodcast nie może mieć postaci xxx.xxx.255.0, a adres sieci xxx.xxx.254.0? Bo jeśli te adresy mogłyby mieć taką postać to wtedy żle byłby wyliczzony adres pierwszego i ostatniego hosta (zwiększam ostatni oktet adresu sieci o 1 i zmniejszam ostatnik oktet broadcastu o 1).

Jeśli chodzi o potęgowanie 2 w pętli to nie pomyślałem o przesunięci bitowym i zrobiłem tak żeby nie liczyć za każdym razem (ograniczenie czasowe na SPOJu)

Pomyśl o ip jak o numerze zapisanym binarnie i o masce, jak o mapie bitowej, w której 1 oznacza 'niezmienny bit adresu' a 0 'zmienny bit adresu'. Poza tym dostajesz w adresacji podsieci spójna pulę adresów, gdzie kazdy następny adres tej puli ma kolejny numer.

Zatem gdybys miał maskę np. 255.255.255.244 (ostatni oktet: 11110100), to miałbyś kolejno adresy (ostani oktet): 0-3 i 8-11, a to są 2 podsieci, zatem:

Maska sieci jest ciągła, patrząc od najstarszego bitu, nie moze być sytuacji, kiedy 0 poprzedza 1. kiedy sie zapalone bity kończą, to się kończą, reszta musi być zgaszona. Maska po prostu jest tym elementem, który określa ilość niezmiennych bitów adresu, inaczej długość niezmiennej części adresu.

Stąd alternatywny zapis ip/maska -> ip/ilosc bitow, np. 10.0.0.0/255.0.0.0 -> 10.0.0.0/8, bo wiadomo, ze 255 to osiem bitów, a te osiem bitów w drugim zapisie jest zapalone i żaden inny.

Broadcast może zawierać cokolwiek, chdzi o to, aby wszystkie zmienne bity były zapalone (odwróć binarnie maskę i zrób sumę logiczną z jakimkolwiek adresem z tej posieci i wychdzi broadcast). Tzn można sobie wygrać broadcast przy konfiguracji sieci, ale taki jest automatycznie domyslny.

adres sieci to piwerwszy adres należący do posieci, czyli ze zgaszonymi wszystkimi bitami zmiennymi.

Stąd naprawde proste operacje nawet nie arytmetyczne, tylko binarne, przesuniecia w lewo, prawo, or, and i not, może czasem xor, coś co sie wykonuje nagminnie na poziomie sterownika, jądra, albo nawet sprzętu nie może być skomplikowane i o to w tym zadaniu ze spoja chodzi, masz wykorzystać te mechanizmy, pokazać, że umiesz operować na bitach.

co do maski 31 i 32, obie maja uzywalne adresy. w sieci /32 jest jeden adres, broadcast trafi tylko do nadawcy i jednocześnie do całej sieci, do jednego hosta, który jest nadawcą. w sieci /31... nigdy takiej nie spotkałem, ale nikt w konću nie zabrania nadać komputerowi adresu sieci.

coś przekombinowałeś wg mnie. masz poprawny:

#include <iostream>

using namespace std;

typedef long long int int64;

int first(int ip, int mask)
{
  return (ip & mask) & 0xFF;
}

int last(int ip, int mask)
{
  return (ip | (~mask)) & 0xFF;
}

int64 count(int a)
{
  int ret = 0;
  for (int i = 0; i<8; i++)
    ret += !(a&(1<<i));
  return ret;
}

int64 combinations(int a, int b, int c, int d)
{
  int64 r = count(a)+count(b)+count(c)+count(d);
  return (1LL<<r)-2LL;
}

int main()
{
  ios_base::sync_with_stdio(0);
  int n;
  cin >> n;
  while (n--)
    {
      int a,b,c,d;
      int ia,ib,ic,id;
      cin >> ia >> ib >> ic >> id >> a >> b >> c >> d;
      int64 cn = combinations(a,b,c,d);
      if (cn<=0)
        cout << 0 << "\n";
      else
        {
          cout << cn << "\n";
          cout << first(ia,a) << "." << first(ib,b) << "." << first(ic,c) << "." << first(id,d)+1 << " "
               << last(ia,a)  << "." << last(ib,b)  << "." << last(ic,c)  << "." << last(id,d)-1  << "\n";
        }
    }
  return 0;
}

24 linie.

#include <stdio.h>
#include <string.h>

int main(){
  char buf[512];
  unsigned long long ipmask;
  while(fgets(buf,512,stdin)){
    buf[strlen(buf)-1]=0;
    char* p=buf;
    while((p=strtok(p," "))){
      ipmask<<=8;
      ipmask|=strtoul(p,0,10);
      p=0;
    }
    unsigned long ipf=(((unsigned long*)&ipmask)[1]&*((unsigned long*)&ipmask))+1;  // +1 na adres sieci
    unsigned long ipl=(((unsigned long*)&ipmask)[1]|(~*((unsigned long*)&ipmask)))-1; // -1 na broadcast
    if(ipl>ipf){ // pierwsze ip ma byc mniejsze od ostatniego w ten sposob zalatwione maski 31 i 32 bity
      fprintf(stdout,"ilosc adresow: %lu\npierwszy adres: %d.%d.%d.%d\nostatni adres: %d.%d.%d.%d\n",(~*((unsigned long*)&ipmask))-1, // mozna jeszcze prosciej policzyc, nie potrzeba logarytmow
      ((unsigned char*)(&ipf))[3],((unsigned char*)(&ipf))[2],((unsigned char*)(&ipf))[1],((unsigned char*)(&ipf))[0],
      ((unsigned char*)(&ipl))[3],((unsigned char*)(&ipl))[2],((unsigned char*)(&ipl))[1],((unsigned char*)(&ipl))[0]);
    }else fprintf(stdout,"ilosc adresow: 0\n");
  }
  return 0;
}

// no tak zapomniałem o pierwszej linijce, ten programik czyta dopoki jest cos na wejsciu (wciaż 24 linie)

#include <stdio.h>
#include <string.h>

int main(){
  char buf[512];
  unsigned long long ipmask;
  unsigned n=(unsigned)strtoul(fgets(buf,512,stdin),0,10);
  while(n-- && fgets(buf,512,stdin)){
    char* p=buf;
    while((p=strtok(p," "))){
      ipmask<<=8;
      ipmask|=strtoul(p,0,10);
      p=0;
    }
    unsigned long ipf=(((unsigned long*)&ipmask)[1]&*((unsigned long*)&ipmask))+1;  // +1 na adres sieci
    unsigned long ipl=(((unsigned long*)&ipmask)[1]|(~*((unsigned long*)&ipmask)))-1; // -1 na broadcast
    if(ipl>ipf){ // pierwsze ip ma byc mniejsze od ostatniego w ten sposob zalatwione maski 31 i 32 bity
      fprintf(stdout,"ilosc adresow: %lu\npierwszy adres: %d.%d.%d.%d\nostatni adres: %d.%d.%d.%d\n",(~*((unsigned long*)&ipmask))-1, // mozna jeszcze prosciej policzyc, nie potrzeba logarytmow
      ((unsigned char*)(&ipf))[3],((unsigned char*)(&ipf))[2],((unsigned char*)(&ipf))[1],((unsigned char*)(&ipf))[0],
      ((unsigned char*)(&ipl))[3],((unsigned char*)(&ipl))[2],((unsigned char*)(&ipl))[1],((unsigned char*)(&ipl))[0]);
    }else fprintf(stdout,"ilosc adresow: 0\n");
  }
  return 0;